#include<bits/stdc++.h>
using namespace std;
const int INF=
0x3f3f3f3f;
int n,m,S,T,dep[
10004],head[
10004],cnt=
0;
struct node{
int to,next,w;
}e[200004];
inline void add(
int u,
int v,
int w){
e[cnt].to=v;e[cnt].next=head[u];e[cnt].w=w;head[u]=cnt++
;
}
inline int bfs(){
queue<
int>
q;
memset(dep,-
1,
sizeof(dep));
dep[S]=
0;q.push(S);
while(!
q.empty()){
int u=
q.front();q.pop();
for(
int i=head[u];i!=-
1;i=
e[i].next){
int v=
e[i].to;
if(dep[v]==-
1&&e[i].w>
0){
dep[v]=dep[u]+
1;
q.push(v);
}
}
}
return dep[T]!=-
1;
}
inline int dfs(
int u,
int c){
if(u==T)
return c;
int f=
0;
for(
int i=head[u];i!=-
1&&f<c;i=
e[i].next){
int v=
e[i].to;
if(e[i].w>
0&&dep[e[i].to]==dep[u]+
1){
int x=dfs(e[i].to,min(e[i].w,c-
f));
f+=
x;
e[i].w-=
x;
e[i^
1].w+=
x;
}
}
if(!f) dep[u]=-
2;
return f;
}
inline int dicnic(){
int ans=
0;
while(bfs()) ans+=
dfs(S,INF);
return ans;
}
int main(){
memset(head,-
1,
sizeof(head));
scanf("%d%d%d%d",&n,&m,&S,&
T);
for(
int i=
1;i<=m;i++
){
int x,y,z;
scanf("%d%d%d",&x,&y,&
z);
add(x,y,z);
add(y,x,0);
}
printf("%d",dicnic());
}
转载于:https://www.cnblogs.com/wifimonster/p/10240525.html
