Tx_Lcy @ 2022-08-13 11:28:09
这个题卡
#include<bits/stdc++.h>
#define int long long
#define rint register int
using namespace std;
int const N=2e2+10;
int const M=1e6+10;
int pre[N],b[N],n,m,head[M],cnt=1,flag[N][N];
struct node{int to,nxt,val;}a[M];
inline void add_edge(int u,int v,int w){
a[++cnt].to=v,a[cnt].val=w,a[cnt].nxt=head[u];
head[u]=cnt,
a[++cnt].to=u,a[cnt].val=0,a[cnt].nxt=head[v],
head[v]=cnt;
}
inline int EK(int s,int t){
int flow=0;
while (1){
for (rint i=1;i<=n;i++) b[i]=0;
queue<int>q;q.push(s),b[s]=1;
int now_flow=1e9;
while (!q.empty()){
int now=q.front();q.pop();
for (rint i=head[now];i;i=a[i].nxt){
int v=a[i].to;
if (a[i].val==0) continue;
if (b[v]) continue;
pre[v]=i,q.push(v);b[v]=1;
now_flow=min(now_flow,a[i].val);
if (v==t) break;
}
}
if (!b[t]) break;
flow+=now_flow;int now=t;
while (now!=s){
a[pre[now]].val-=now_flow,
a[pre[now]^1].val+=now_flow,
now=a[pre[now]^1].to;
}
}
return flow;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int s,t,u,v,w;cin>>n>>m>>s>>t;
while (m--){
cin>>u>>v>>w;
if (flag[u][v]==0) add_edge(u,v,w),flag[u][v]=cnt;
else a[flag[u][v]-1].val+=w;
}
cout<<EK(s,t)<<'\n';
return 0;
}