求助玄学问题
查看原帖
求助玄学问题
555065
ChrysanthBlossom楼主2023/8/4 22:13

这是一份#10会TLE的代码:

#include<bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const ll maxn=2e2+5,maxm=1e4+5,inf=2147483647;
int n,m,s,t;
int cnt,head[maxn],nxt[maxm],to[maxm];
ll bq[maxm];
void add(int u,int v,int w){
	++cnt;
	to[cnt]=v;
	nxt[cnt]=head[u];
	bq[cnt]=w;
	head[u]=cnt;
}
int flag[maxn][maxn];
ll flow;
ll dis[maxn],pre[maxn];
bool vis[maxn];
bool bfs(){
	memset(vis,0,sizeof(vis));
	for(ri i=1;i<=n;i++)dis[i]=inf;
	memset(pre,0,sizeof(pre));
	queue<int>q;
	q.push(s);
	vis[s]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(ri e=head[u];e;e=nxt[e]){
			int v=to[e];
			ll w=bq[e];
			if(!w||vis[v])continue;
			pre[v]=u;
			dis[v]=min(dis[u],w);
			vis[v]=1;
			q.push(v);
			if(v==t)return 1;
		}
	}return 0;
}
void update(){
	int v=t;
	while(v^s){
		int u=pre[v];int b=flag[u][v];
		bq[b]-=dis[t];bq[b^1]+=dis[t];
		v=u;
	}flow+=dis[t];
}
void EK(){
	while(bfs()){
		update();
	}
}
signed main(){
	//freopen("lg.in","r",stdin);
	//freopen("lg.out","w",stdout);
	ios::sync_with_stdio(0);
	cin>>n>>m>>s>>t;
	cnt=1;
	for(ri i=1,u,v,w;i<=m;i++){
		cin>>u>>v>>w;
		if(flag[u][v]){
			bq[flag[u][v]]+=w;
		}else{
			add(u,v,w);
			flag[u][v]=cnt;
			add(v,u,0);
		}
	}
	EK();
	cout<<flow;
	//fclose(stdout);
    return 0;
}

可是当我把 if(!w||vis[v])continue; 改成 if(w<=0||vis[v])continue; 时,居然神奇的AC了

这也就意味着有w是负的,但是似乎没有一个地方会把w变负,于是就蒙圈了。

本来想着可能是炸了int,结果define了还是TLE

哪位大佬能解释一下?谢谢

2023/8/4 22:13
加载中...