hllh @ 2019-06-01 20:20:17
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct xx{
int from,to,data,nxt;
}e[200005];
queue<int>q;
int inf=100000007;
int n,m,s,T,tot=1,v[10005],level[10005];
void add(int a,int b,int c)
{
e[++tot].from=a;
e[tot].to=b;
e[tot].data=c;
e[tot].nxt=v[a];
v[a]=tot;
}
bool bfs()
{
memset(level,-1,sizeof(level));
q.push(s);level[s]=0;
while(!q.empty())
{
int k=q.front();q.pop();
for(int j=v[k];j;j=e[j].nxt)
{
int t=e[j].to;
if(e[j].data!=0&&level[t]==-1)
{
level[t]=level[k]+1;
q.push(t);
}
}
}
if(level[T]!=-1) return true;
else return false;
}
int dfs(int u,int flow)
{
if(u==T) return flow;
int ret=flow;
for(int j=v[u];j;j=e[j].nxt)
{
if(ret<=0) break;
int t=e[j].to;
if(e[j].data!=0&&level[t]==level[u]+1)
{
int k=dfs(t,min(e[j].data,ret));
ret-=k;e[j].data-=k;e[j^1].data+=k;
}
}
return flow-ret;
}
void dinic()
{
int maxflow=0;
while(bfs()==true)
{
maxflow+=dfs(s,inf);
}
printf("%d\n",maxflow);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&T);
for(int i=1;i<=m;++i)
{
int ui,vi,wi;
scanf("%d%d%d",&ui,&vi,&wi);
add(ui,vi,wi);add(vi,wi,0);
}
dinic();
return 0;
}
by hllh @ 2019-06-01 20:25:47
数据。。。。。。
这都能过7个点
add(ui,vi,wi);add(vi,wi,0);
by oxbby @ 2019-07-22 11:53:24
怎么这么巧,我也是这个错误,看了好久都看不出来,直到看到这篇讨论……