EndA @ 2018-07-10 21:06:53
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int MAX=1e6;
inline int readInt(void){
int num=0;char c=getchar();
while(c<'0'||c>'9'){c=getchar();}
while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
return num;
}
int cnt=0;
int nex[MAX+10];
int hed[MAX+10];
int pow[MAX+10];
int nod[MAX+10];
inline void addEdge(int u,int v,int p){
nex[++cnt]=hed[u];hed[u]=cnt;nod[cnt]=v;pow[cnt]=p;
nex[++cnt]=hed[v];hed[v]=cnt;nod[cnt]=u;pow[cnt]=0;
}
int n,m,s,t;
int vis[MAX+10];
void read(void);
void solve(void);
int DFS(int,int,int);
int main(void){
read();
solve();
return 0;
}
void read(void){
n=readInt();m=readInt();s=readInt();t=readInt();
for(int i=1;i<=m;i++){
int u=readInt();int v=readInt();int p=readInt();addEdge(u,v,p);
}
}
void solve(void){
int flo=0;
while(true){
memset(vis,0,sizeof(vis));
int f=DFS(s,t,MAX);
if(f==0) {printf("%d",flo);return;}
flo+=f;
}
}
int DFS(int cur,int t,int f){
if(cur==t) return f;
vis[cur]=1;
for(int i=hed[cur];i;i=nex[i]){
if(i%2==0) continue;
if(vis[nod[i]]==0&&pow[i]>0){
int d=DFS(nod[i],t,min(f,pow[i]));
if(d>0){
pow[i]-=d;
pow[i^1]+=d;
return d;
}
}
}
return 0;
}
by 良月澪二 @ 2018-07-10 21:30:37
by moye到碗里来 @ 2018-07-10 21:47:54
@LinkedIn i%2 == 0 为什么要continue,你这不就走不了回流的弧了么..
by 良月澪二 @ 2018-07-10 21:50:47
艾特我干嘛...
by moye到碗里来 @ 2018-07-10 21:52:24
@LinkedIn 点错了..2333 @EndA
by EndA @ 2018-07-13 21:19:59
@moye到碗里来 懂了,3q
by EndA @ 2018-07-13 21:42:57
@LinkedIn what?
by EndA @ 2018-07-13 22:09:40
@moye到碗里来 改了之后暴zero....... 5555
by moye到碗里来 @ 2018-07-14 10:15:59
@EndA 那我也不知道啊。。。
by EndA @ 2018-07-14 11:23:08
@moye到碗里来 改对了,那个i^1表示的不是同一条边。。。。
by moye到碗里来 @ 2018-07-14 12:17:47
@EndA 233