wubaiting2020 @ 2019-05-03 16:14:18
RT,我用的Dinic
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int n,m,ss,tt;
int h[200005],cnt=0;
int num[200005];//num记录点的层
struct node{int nx,to,v;}w[200005];
void AddEdge(int x,int y,int z){w[++cnt].to=y;w[cnt].v=z;w[cnt].nx=h[x];h[x]=cnt;}
int BFS(int s,int t)
{
queue<int>q;
memset(num,-1,sizeof(num));
num[s]=0;//初始化
q.push(s);
while(!q.empty())
{
int x=q.front();q.pop();
if(x==t)return 1;
for(int i=h[x];i;i=w[i].nx)
{
int y=w[i].to;
if(num[y]==-1&&w[i].v>0){num[y]=num[x]+1;q.push(y);}
}
}
return 0;
}
int DFS(int x,int t,int maxx)
{
int ans=0,d=0;
if(x==t)return maxx;
for(int i=h[x];i;i=w[i].nx)
{
int y=w[i].to;
if(w[i].v>0&&num[y]==num[x]+1)//必须按层序走才能保证最短路
{
d=DFS(y,min(w[i].v,maxx),t);
w[i].v-=d;
w[i^1].v+=d;//更新正向弧和反向弧的容量
ans+=d;
maxx-=d;
if(maxx==0)return ans;
}
}
return ans;
}
void Dinic()
{
int ans=0;
while(BFS(ss,tt))ans+=DFS(ss,tt,0x3f3f3f3f);
printf("%d",ans);
}
int main()
{
scanf("%d %d %d %d",&n,&m,&ss,&tt);
for(int i=1;i<=m;i++)
{
int xx,yy,zz;
scanf("%d %d %d",&xx,&yy,&zz);
AddEdge(xx,yy,zz);
AddEdge(yy,xx,0);
}
Dinic();
return 0;
}
by aminoas @ 2019-05-03 16:14:56
头像好评
by Soledad_S @ 2019-05-03 16:22:24
头像好评
by c2020HXW @ 2019-05-03 16:26:34
头像好评
by liuyifan @ 2019-05-03 16:29:14
头像好评
by qsmoonzh @ 2019-05-03 16:31:39
头像好评
by zyzzyzzyzzyz @ 2019-05-03 16:32:40
@wubaiting2020 cnt要从0开始吧
by zyzzyzzyzzyz @ 2019-05-03 16:33:22
从1开始,不是0
by wubaiting2020 @ 2019-05-03 16:44:22
谢谢,我过了
d=DFS(y,min(w[i].v,maxx),t);
这句话传参的顺序错了
by wubaiting2020 @ 2019-05-03 16:44:29
@zyzzyzzyzzyz
by zyzzyzzyzzyz @ 2019-05-03 16:50:49
@wubaiting2020 这种错误也是无语了。。。
多路增广好评,没有当前弧优化差评