FF全WA求助/kk
查看原帖
FF全WA求助/kk
327444
3a51_楼主2022/6/2 15:33

萌新初学网络流,参考了下题解

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Mod1=998244353;
const int Mod2=1000000007;
const int Inf=1e18;
int gcd(int a,int b){return __gcd(a,b);}
int lcm(int a,int b){return a/gcd(a,b)*b;}
const int N=205;
const int M=10005;
int to[M],nxt[M],val[M],lst[N],cnt,vis[N],n,m,s,t; 
void add(int u,int v,int w){
	to[++cnt]=v;
	val[cnt]=w;
	nxt[cnt]=lst[u];
	lst[u]=cnt;
}
int dfs(int u,int now){
	if(u==t) return now;
	vis[u]=1;
	for(int i=lst[u];i!=0;i=nxt[i]){
		int v=to[i];
		if(vis[v]==1) continue;
		int p=dfs(v,min(now,val[i]));
		if(p>0){
			val[i]-=p;
			val[i+1]+=p;
			return p;
		}
	}
	return 0;
}
void Solve(){
	//coding here...
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,0);
	}
	int ans=0;
	int p=dfs(s,Inf);
	while(p>0){
		memset(vis,0,sizeof(vis));
		ans+=p;
		p=dfs(s,Inf);
	}
	cout<<ans<<endl;
}
signed main(){
	ios::sync_with_stdio(false);
	int _;
	//cin>>_;
	_=1;
	while(_--){
		Solve();
	}
	return 0;
}
//STO 来看我程序的人 Orz
2022/6/2 15:33
加载中...