shitbro @ 2019-09-30 14:06:25
DINIC 未知错误???无法输出
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf=1<<30;
int n,m,s,t;
int cnt=1,maxflow=0;
int head[100005],dep[100005],inque[100005];
struct node{
int last,to,val;
}tree[100005];
void add(int x,int y,int z)
{
tree[++cnt].last=head[x];
tree[cnt].to=y;
tree[cnt].val=z;
head[x]=cnt;
}
bool D_pre()
{
memset(dep,0x3f,sizeof dep);
memset(inque,0,sizeof inque);
dep[s]=0;
queue <int> q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
inque[u]=0;
for(int i=head[u];i;i=tree[i].last)
{
int d=tree[i].to;
if(dep[d]>dep[u]+1&&tree[i].val)
{
dep[d]=dep[u]+1;
if(!inque[d])
{
q.push(d);
inque[d]=1;
}
}
}
}
if(dep[t]!=0x3f3f3f3f)
return 1;
return 0;
}
int D_dfs(int u,int flow)
{
int low=0;
if(u==t)
{
maxflow+=flow;
return flow;
}
int used=0;
for(int i=head[u];i;i=tree[i].last)
{
int d=tree[i].to;
if(tree[i].val&&dep[d]==dep[u+1])
{
if(low=D_dfs(d,min(flow-used,tree[i].val)))
{
used+=low;
tree[i].val-=low;
tree[i^1].val+=low;
if(used==flow)
break;
}
}
}
return used;
}
int dinic()
{
while(D_pre())
{
D_dfs(s,inf);
}
return maxflow;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,0);
}
printf("%d",dinic());
return 0;
}
by bellmanford @ 2019-09-30 14:14:47
@larry❤DVA 好像这是EK吧
by shitbro @ 2019-09-30 14:16:14
@bellmanford
是dinic
是多路增广
by shitbro @ 2019-09-30 14:16:59
@142857cs
by shitbro @ 2019-09-30 14:17:45
@142857cs au爷求助
by shitbro @ 2019-09-30 14:20:46
有人吗????
by bellmanford @ 2019-09-30 14:22:36
神奇,我打网络流用EK的bfs和Dinic的dfs都在这
吐槽而已QwQ
by shitbro @ 2019-09-30 14:26:24
@bellmanford bfs是找是否有增广路 dfs是处理
by bellmanford @ 2019-09-30 14:32:44
只是吐槽啦
by 辰星凌 @ 2019-09-30 15:25:33
if(tree[i].val&&dep[d]==dep[u+1])
改为dep[d]==dep[u]+1
by 辰星凌 @ 2019-09-30 15:26:05
@辰星凌 漏了,是if(tree[i].val&&dep[d]==dep[u]+1)