Arcturus1350 @ 2018-05-01 16:38:27
代码表示在求分层图求最小割。 但是最小割不是等于最大流么??? 然后BZOJ1001过了。改完建边放到这里WA了。。。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int cnt=2;
int alist[6000001];
struct data{
int v;int next;int value;
}edge[6000001];
void add(int u,int v,int value)
{
edge[cnt].v=v;
edge[cnt].value=value;
edge[cnt].next=alist[u];
alist[u]=cnt++;
return ;
}
int h[1000001];
int q[1000001];
bool bfs()
{
int x,next;
memset(h,-1,sizeof(h));
int head=0,tail=1;
q[head]=1;
h[1]=0;
while(head<tail)
{
x=q[head++];
next=alist[x];
while(next)
{
int v=edge[next].v;
int value=edge[next].value;
if(value&&h[v]<0)
{
q[tail++]=v;
h[v]=h[x]+1;
}
next=edge[next].next;
}
}
// for(int i=1;i<=n*m;i++) printf("h[%d]=%d\n",i,h[i]);
if(h[m]==-1) return false;
return true;
}
int ans;
int dfs(int x,int y)
{
if(x==m) return y;
int next=alist[x];
int w,used=0;
while(next)
{
int v=edge[next].v;
int value=edge[next].value;
if(value&&h[v]==h[x]+1)
{
w=y-used;
w=dfs(v,min(w,value));
edge[next].value-=w;
edge[next^1].value+=w;
used+=w;
if(used==y) return y;
}
next=edge[next].next;
}
if(!used) h[x]=-1;
return used;
}
void dinic()
{
while(bfs()) ans+=dfs(1,0x7fffffff);
}
int n1,m1,e1;
int main()
{
scanf("%d%d%d%d",&n1,&m1,&m,&n);
for(int i=1;i<=m1;i++)
{
int u,v,val;
scanf("%d%d%d",&u,&v,&val);
add(u,v,val);
add(v,u,val);
}
dinic();
printf("%d",ans);
return 0;
}
by かなで @ 2018-05-01 16:48:20
@cn:苏卿念 虽然并不会Dinic...
但dalao您确定您反向边建对了??
by Niko @ 2018-05-01 17:08:01
add(v,u,val);
手动滑稽
by YoungNeal @ 2018-05-01 17:11:42
add(v,u,val)
手动滑稽
by henry_y @ 2018-05-01 17:45:09
真的觉得您找个正常一点的板子来写比较好,这种反向边...您写个add(v,u,0)不好么..