starusc @ 2018-06-02 09:23:18
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define N 4000010
#define INF (long long )200000000000000
struct edge{
int v,next;long long c;
}e[2*N];
int n,m,s,t,dis[N];//层数
int first[N]={0},cnt=1,cur[N];
void add(int u,int v,long long c){
e[++cnt].v=v;e[cnt].c=c;
e[cnt].next=first[u];first[u]=cnt;
}
int bfs(){//编写层数
queue<int>q;
q.push(s);
memset(dis,-1,sizeof(dis));
dis[s]=0;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=first[u];i;i=e[i].next){//
int v=e[i].v;//
if(e[i].c>0&&dis[v]==-1){
dis[v]=dis[u]+1;
q.push(v);
if(v==t)return 1;//到终点结束
}
}
}
return 0;
}
int dfs(int x,long long f){//当前点 最小残量
if(x==t||f==0)return f;//到终点或死路
long long used=0;//当前点已流出流量
for(int &i=cur[x];i;i=e[i].next){
if(e[i].c&&dis[e[i].v]==dis[x]+1){//有流量且满足层数要求
long long w=dfs(e[i].v,min(f,(long long)e[i].c));
if(!w)continue;//死路
used+=w;
e[i].c-=w;e[i^1].c+=w;//正反边 x^1=比x大1大奇数或比x小1的偶数
if(f==used)break; //用完所有流量不必再跑
}
}
if(!used)dis[x]=-1;//优化:无用的省略
return used;
}
long long dinic(){
long long flow=0;
while(bfs()){//终点有层数——>还有路
memcpy(cur,first,sizeof(first));
flow+=dfs(s,INF);//增广路
}
return flow;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>s>>t;
int u,v,c;
for(int i=1;i<=m;i++){
cin>>u>>v>>c;
add(u,v,c);//正
add(v,u,0);//反
}
int r=dinic();
cout<<r;//最大流
return 0;
}