{
for (int i = 0; i < n; i++) maxf += f[s][i]; break; } }
return maxf; }
int main() {
freopen(\ freopen(\ init();
int ans = Edmonds_karp(); printf(\ return 0; } 3.3 Dinic算法 3.3.1算法介绍与分析
Dinic算法是从带发点Vs和收点Vt的容量网络S的任一可行流f0 (例如零流)开始，构造S的关于f0的分层增量网络AS(f0)，在AS(f0)中找一条从Vs到Vt的增广路
1f0径u，对f沿u进行增广得到可行流，在AS(f)中删去u上容量最小的弧，并相
0
0
11ff00应修改AS(f0)上弧的容量，得到网络AS()，然后可以在AS()中再找一条从Vs
12ff00到V的增广路径u，对沿u进行增广得到可行流，重复上述步骤依次得到S的
t
可行流
f01,f02,,f0p?f1，因为AS(f0)只有有限条弧，每次至少删一条，所以有限步
后必然会使剩下的网络不再存在增广路径，Vt在AS(f1)中的层数一定大于它在AS(f0)中的层数；针对AS(f1)重复上面的做法，在有限次增广后一定会得到S的可行流f2，使Vt在AS(f2)中的层数更大。由于Vt的层数最多为n?1（n是网络S的顶点数）。所以经过有限步后得到S的可行流fk，S中不再有fk的增广链，这时fk就是S的最大流
11
[2,12,13]
。
Dinic算法的具体步骤如下： 1、初始化流量，计算出剩余图
2、根据剩余图计算层次图。若汇点不在层次图内，则算法结束 3、在层次图内用一次dfs过程增广 4、转步骤2 下面是dfs的过程： p←s;
While outdegree(s)>0 u←p.top; if u<>t
if outdegree(u)>0
设(u,v)为层次图中的一条边; p←p,v; else
从p和层次图中删除点u, 以及和u连接的所有边; else
增广p（删除了p中的饱和边）; 令p.top为p中从s可到达的最后顶点; end while
在程序里，p表示找到的增广路径，p.top为路径中的最后一个定点。一开始，P中只有源点。
整个While循环分为2个操作。如果p的最后一个顶点为汇点，也就是说找到了增广路，那么对p增广，注意到增广后一定有一条或多条p中的边被删除了。这时，我们使增广路径后退至p中从源点可到达的最后一个顶点。如果p的最后一个顶点不为汇点，那么观察最后那个的顶点u 。若在层次图中存在从u连出的一条边，比如(u,v)，我们就将顶点v放入路径p中，继续dfs遍历；否则，点u对之后的dfs遍历就没有用了，我们将点u以及层次图中连到u的所有边删除，并且在p中后退一个点。Dfs过程将会不断重复这2个操作，直到从源点连出的边全部被删除为止[14]。
2 1
由于在Dinic算法的执行中，每次都要重新分层，汇点所在的层次也是严格递增的，而且n个点的层次图最多有n层，所以Dinic算法最多重新分层n次。在层次图中，因为每条增广路径都有瓶颈，而且两次增广的瓶颈都不可能一样，所以增广路径最多有m条。搜索每一条增广路径时，回溯和前进都最多有n次，因此时间复杂度是O(nm)；而沿着同一条路径(i,j)不可能枚举两次，因为第一次枚举的时候要么这条边的容量已经用尽，要么j到汇点不存在通路从而使其从这一层次图中被删除[15]。综上所述Dinic算法时间复杂度理论的上界是O(n2*m)，其中m为弧的数目，n是迭代次数，是多项式算法。邻接表表示图，空间复杂度为（n+m）。
Dinic算法是将顶点按照其与发点的最短距离分层，分层时用的宽度优先法，而寻求增广路径时则采用深度优先策略。 3.3.2算法实现
下面是dinic的代码实现： #include
const int INF=0x3f3f3f3f; int s[N][N]; int d[N]; int n,m;
int min(int a,int b) {
return a bool bfs() { queue memset(d,-1,sizeof(d)); 3 1 d[1]=0; Q.push(1); while(!Q.empty()){ int v=Q.front();Q.pop(); for(int i=1;i<=n;i++){ if(d[i]==-1&&s[v][i]){ d[i]=d[v]+1; Q.push(i); } } } return d[n]!=-1; } int dfs(int v,int cur_flow) { int dt=cur_flow; if(v==n)return cur_flow; for(int i=1;i<=n;i++){ if(s[v][i]>0&&d[v]+1==d[i]){ int flow=dfs(i,min(dt,s[v][i])); s[v][i]-=flow; s[i][v]+=flow; dt-=flow; } } return cur_flow-dt; } int dinic() { int cur_flow,ans=0; 4 1
相关推荐：
loading