萌新初学网络流,参考了下题解。
#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