ISAP WA一个看起来很正常点
查看原帖
ISAP WA一个看起来很正常点
34225
bulijoijiodibuliduo楼主2021/6/1 21:34

基本抄刘汝佳蓝书上的代码,略有改动,结果WA了一个点。那个点的数据看起来很正常。应该没什么特殊情况。哪位奆老来帮帮忙!

#include<bits/stdc++.h>
#define int long long
const int N=5e4+10,M=2e5+10,inf=2e9;
using namespace std;
int now[N],head[N],to[M],nxt[M],cap[M],tot=1,d[N],pre[N],s,t,gap[N],n,e;
void addedge(int u,int v,int c){
	tot++;
	to[tot]=v;
	cap[tot]=c;
	nxt[tot]=head[u];
	head[u]=tot;
}
void add(int u,int v,int c){
	addedge(u,v,c);
	addedge(v,u,0);
}
void bfs(){
	queue<int>q;
	q.push(t);
	d[t]=1;
	while(!q.empty()){
		int x=q.front();
		now[x]=head[x];
		q.pop();
		for(int i=head[x];i;i=nxt[i]){
			int y=to[i],c=cap[i];
			if(c==0&&!d[y]){
				d[y]=d[x]+1;
				q.push(y);
			}
		}
	}
	for(int i=1;i<=n;i++){
		d[i]--;
	}
}
int aug(){
	int x=t;
	int flow=inf;
	while(x!=s){
		flow=min(flow,cap[pre[x]]);
		x=to[1^pre[x]];
	}
	x=t;
	while(x!=s){
		cap[pre[x]]-=flow;
		cap[pre[x]^1]+=flow;
		x=to[1^pre[x]];
	}
	return flow;
}
int maxflow(){
	bfs();
	int x=s,flow=0;
	for(int i=1;i<=n;i++){
		gap[d[i]]++;
	}
	while(d[s]<n){
		if(x==t){
			flow+=aug();
			x=s;
		}
		bool ok=0;
		for(int i=now[x];i;i=nxt[i]){
			int c=cap[i],y=to[i];
			if(c&&d[x]==d[y]+1){
				ok=1;
				pre[y]=i;
				now[x]=i;
				x=y;
				break;
			}
		}
		if(!ok){
			int m=n-1;
			for(int i=head[x];i;i=nxt[i]){
				int y=to[i],c=cap[i];
				if(c)m=min(m,d[y]);
			}
			if(--gap[d[x]]==0)break;
			gap[d[x]=m+1]++;
			now[x]=head[x];
			if(x!=s)x=to[pre[x]^1];
		}
	}
	return flow;
}
signed main(){
	cin>>n>>e>>s>>t;
	for(int i=0;i<e;i++){
		int u,v,c;
		cin>>u>>v>>c;
		add(u,v,c);
	}
	cout<<maxflow();
}

2021/6/1 21:34
加载中...