蓝莲花__ @ 2019-10-11 16:16:44
#include<bits/stdc++.h>
using namespace std;
const int mx=100010,MAX=1e9;
int n,m,s,t,tot=-1;
int h[mx],d[mx],cur[mx];
struct node{int nxt,to,w;}e[mx<<1];
queue<int> q;
void add(int x,int y,int cc)
{
e[++tot].nxt=h[x];
e[tot].to=y;
e[tot].w=cc;
h[x]=tot;
}
bool bfs()
{
for (int i=1;i<=n;i++) d[i]=-1,cur[i]=h[i];
d[s]=1;q.push(s);
while (!q.empty())
{
int x=q.front();
q.pop();
for (int i=h[x];i;i=e[i].nxt)
{
int y=e[i].to;
if (d[y]==-1 && e[i].w)
{
d[y]=d[x]+1;
q.push(y);
}
}
}
if (d[t]==-1) return false;
return true;
}
int dfs(int x,int lim)
{
if (x==t || lim==0) return lim;
int flow=0,f;
for (int i=cur[x];i;i=e[i].nxt)
{
cur[x]=i;
int y=e[i].to;
if (d[y]==d[x]+1 && e[i].w)
{
f=dfs(y,min(lim,e[i].w));
flow+=f;
lim-=f;
e[i].w-=f;
e[i^1].w+=f;
if (!lim) break;
}
}
return flow;
}
int main()
{
cin>>n>>m>>s>>t;
for (int i=1;i<=m;i++)
{
int x,y,cc;
cin>>x>>y>>cc;
add(x,y,cc);
add(y,x,0);
}
int ans=0;
while (bfs()) ans+=dfs(s,MAX);
cout<<ans;
return 0;
}
/*
10 25 3 1
9 3 80
5 10 62
4 2 13
7 2 20
3 10 90
6 10 53
2 3 11
6 3 45
9 5 37
10 9 93
7 8 28
4 5 28
1 2 52
4 5 54
1 2 62
7 4 64
4 3 40
7 3 39
8 2 72
7 5 5
3 6 88
3 2 56
9 2 72
2 1 81
6 7 84
*/
by wmy_goes_to_thu @ 2019-10-11 16:20:47
正常,比如一道题叫做大吉大利,晚上吃鸡
by wmy_goes_to_thu @ 2019-10-11 16:21:09
P4061
by 莫奈的崖径 @ 2019-10-11 16:29:24
我只能说tql