loris @ 2020-01-28 10:32:51
#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
struct edge
{
int to;
int nxt;
int c;
}e[550000];
int p[200001],k=1;
bool used[200001];
void add(int u,int v,int w)
{
e[k].nxt=p[u];
p[u]=k;
e[k].to=v;
e[k].c=w;
k++;
}
int dfs(int s,int t,int f)
{
if(s==t)
return f;
used[s]=1;
for(int i=p[s];i!=0;i=e[i].nxt)
{
if(!used[e[i].to]&&e[i].c>0)
{
int d=dfs(e[i].to,t,min(f,e[i].c));
if(d>0)
{
e[i].c-=d;
add(e[i].to,s,d);
return d;
}
}
}
return 0;
}
int get_maxf(int s,int t)
{
int maxf=0;
int f;
while(1)
{
memset(used,0,sizeof(used));
f=dfs(s,t,INF);
if(f==0)
return maxf;
maxf+=f;
}
}
int main()
{
int n,m,s,t,u,v,w;
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
add(u,v,w);
}
cout<<get_maxf(s,t);
return 0;
}
by 宁_缺 @ 2020-02-02 23:20:09
@loris
很高兴遇到一个和我一样路径数复制为1的,但这样你就要多开一个,不然就爆了
其他貌似都对的
by loris @ 2020-02-03 09:30:18
Thanks♪(・ω・)ノ