hamster000 @ 2024-03-20 00:15:00
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M=100005;
const int N=1005;
int h[N],v[M],w[M],nxt[M];
int mf[N],pre[N];
int idx=1;
void add(int a,int b,int c){
v[++idx]=b;
w[idx]=c;
nxt[idx]=h[a];
h[a]=idx;
}
int n,m,S,T;
bool bfs(){
memset(mf,0,sizeof(mf));
mf[S]=1e9;
queue<int> q;
q.push(S);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=h[u];i;i=nxt[i]){
if(!mf[v[i]]&&w[i]){
mf[v[i]]=min(mf[u],w[i]);
pre[v[i]]=i;
q.push(v[i]);
if(v[i]==T){
return 1;
}
}
}
}
return 0;
}
ll EK(){
ll flow=0;
while(bfs()){
int tmp=T;
while(tmp!=S){
int i=pre[tmp];
w[i]-=mf[tmp];
w[i^1]+=mf[tmp];
tmp=v[i^1];
}
flow+=mf[T];
}
return flow;
}
int main(){
cin >> n >> m >> S >> T;
while(m--){
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
add(b,a,0);
}
cout << EK() << endl;
}
by L_zaa_L @ 2024-03-20 08:24:33
@hamster000
w[i]-=mf[tmp];
w[i^1]+=mf[tmp];
应该减去 mf[T]
by __Cby___ @ 2024-03-20 12:29:36
w[i]-=mf[tmp];
w[i^1]+=mf[tmp];
变成
w[i]-=mf[T];
w[i^1]+=mf[T];
by hamster000 @ 2024-03-20 22:50:09
@__Cby___ 怪我眼瞎没跳出来,谢了各位。