蒟蒻求出 EK 19pts WA
查看原帖
蒟蒻求出 EK 19pts WA
241867
wtcqwq楼主2022/1/24 10:02

rt

哪位大佬帮我调一下,非常感谢

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=200009;
const ll N=50009;
struct edge{
    ll to,c,nxt;
}e[M*2];
ll flow[N],pre[N];
ll hd[N];
ll S,T,nE=1,n,m;
const ll INF=1e9;
void add(ll u,ll v,ll c){
	e[++nE]=(edge){v,c,hd[u]};
	hd[u]=nE;
} 
bool bfs(){
	fill(pre,pre+1+n,0);
	queue<ll> q;
	q.push(S);
	pre[S]=-1;
	flow[S]=INF;
	while(!q.empty()){
		ll u=q.front(); q.pop();
		for(int i=hd[u];i;i=e[i].nxt){
			ll c=e[i].c;
			if(!c)continue;
			ll v=e[i].to;
			if(pre[v])continue;
			q.push(v);
			pre[v]=i;
			flow[v]=min(flow[u],c);
			if(v==T)return 1;
		}
	}
	return 0;
}
void EdmondKarp(){
	ll maxFlow=0;
	while(bfs()){
		maxFlow+=flow[n];
		for(int u=T;u!=S;u=e[pre[u]^1].to){
			e[pre[u]].c-=flow[T];
			e[pre[u]^1].c+=flow[T]; 
		}
	}
	cout<<maxFlow<<endl;
}
int main(){
    cin>>n>>m>>S>>T;
    for(int i=1;i<=m;i++){
    	ll u,v,c;
    	cin>>u>>v>>c;
    	add(u,v,c);
    	add(v,u,0);
	}
	EdmondKarp();
	return 0;
}
2022/1/24 10:02
加载中...