———————————————————————-
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
void add(int x,int y,int z)//一条从x到y容量为z的边 { tot++;//要注意tot初值为1 Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } bool bfs() { int t=0,w=1; memset(h,-1,sizeof(h));//h数组为每个点的层次 x[1]=S;h[S]=0; while (t!=w) { int u=x[++t]; for (int i=head[u];i;i=Next[i]) if (val[i]!=0&&h[tree[i]]==-1)//这条边容量不为0且tree[i]未访问过 { x[++w]=tree[i];//加入队列 h[tree[i]]=h[u]+1;//更新点的层次 } } return h[T]!=-1; } long long dfs(int u,long long low)//u为当前点，low为当前条增广路中容量最小的边的容量 { if (u==T) return low;//如果到了汇点就返回low long long used=0;//流经当前点u的流量 for (int i=cur[u];i;i=Next[i])//cur[u]为当前弧优化 if (val[i]>0) { int v=tree[i]; if (h[v]==h[u]+1)//对于当前层次图，只到下一层的点 { long long w=dfs(v,min(val[i],low-used)); //由于dinic算法一次找多条增广路，所以low-used为这整条增广路中剩余的流量 //w为最终一条增广路中用掉的流量 val[i]-=w;val[i^1]+=w;//修改残余网络 used+=w;//这整条增广路中已用流量增加w cur[u]=i;//当前弧优化，下一次从这条边开始增流 if (used==low) return low;//用完了就返回最终用掉的流量 } } if (used==0) h[u]=-1;//根本增加不了最大流量就不用跑了 return used;//如果没到汇点就是0 } void dinic() { while (bfs())//建立层次图 { for (int i=1;i<=n;i++) cur[i]=head[i];//当前弧优化，开始时先附为边表的第一个 ans+=dfs(S,1LL<<60);//开始时low定为∞ } } |
模板（与上面的代码有一些不同）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
namespace DINIC { int S,T,tot=1,Next[M],head[N],tree[M],val[M],Queue[N],h[N],cur[N]; void add(int x,int y,int z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } void add_edge(int x,int y,int z) { add(x,y,z); add(y,x,0); } bool bfs() { int t=0,w=1; memset(h,-1,sizeof(h)); Queue[1]=S;h[S]=0; while (t!=w) { int u=Queue[++t]; for (int i=head[u];i;i=Next[i]) if (val[i]!=0) { int v=tree[i]; if (h[v]==-1) { Queue[++w]=v; h[v]=h[u]+1; } } } return h[T]!=-1; } int dfs(int u,int low) { if (u==T) return low; int used=0; for (int i=cur[u];i;i=Next[i]) { cur[u]=i; int v=tree[i]; if (val[i]>0&&h[v]==h[u]+1) { int w=dfs(v,min(val[i],low-used)); val[i]-=w;val[i^1]+=w; used+=w; if (used==low) return low; } } if (used==0) h[u]=-1; return used; } int dinic() { int ans=0; while (bfs()) { for (int i=1;i<=T;i++) cur[i]=head[i]; ans+=dfs(S,1<<29); } return ans; } } |
Tips:在每次将cur[i]赋值为head[i],T在这里是最大编号。
