huangx607087 @ 2019-08-06 22:46:40
#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,A;
int e[950000],w[950000],hd[950000],nxt[950000];
int q[3350000],step[950000];
bool bfs()
{
int f=1,r=1;
memset(q,0,sizeof(q));
memset(step,0,sizeof(step));
step[s]=1,q[1]=s;
while(f<=r)
{
int x=q[f++],k=hd[x];
while(k)
{
if(step[e[k]]==0&&w[e[k]]>0)
{
step[e[k]]=step[x]+1;
q[++r]=e[k];
}
k=nxt[k];
}
}
return step[t];
}
int dfs(int x,int flow)
{
if(x==t) return flow;
int k=hd[x];
while(k)
{
if(w[k]&&step[e[k]]==step[x]+1)
{
int dis=dfs(e[k],min(flow,w[k]));
if(dis>0)
{
w[k]-=dis;
if(k%2) w[k+1]+=dis;
else w[k-1]+=dis;
return dis;
}
}
k=nxt[k];
}
return 0;
}
void dinic()
{
int B=0;
while(bfs())
{
while(B=dfs(s,20011230)) A+=B;
}
}
int main()
{
int i,j,k=0;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
e[++k]=y,w[k]=z,nxt[k]=hd[x],hd[x]=k;
e[++k]=x,w[k]=0,nxt[k]=hd[y],hd[y]=k;
}
dinic();
printf("%d\n",A);
return 0;
}
by Vn_nV @ 2019-08-06 22:48:15
自己调