糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

Dinic 算法模板

Dinic算法是一种比较容易实现的,相对比较快的最大流算法。
今天看了一下它的原理,发现的确很牛逼。

求最大流的本质,就是不停的寻找增广路径。直到找不到增广路径为止。
对于这个一般性的过程,Dinic算法的优化如下:

(1)
Dinic算法首先对图进行一次BFS,然后在BFS生成的层次图中进行多次DFS。
层次图的意思就是,只有在BFS树中深度相差1的节点才是连接的。
这就切断了原有的图中的许多不必要的连接。很牛逼!
这是需要证明的,估计证明也很复杂。

(2)
除此之外,每次DFS完后,会找到路径中容量最小的一条边。
在这条边之前的路径的容量是大于等于这条边的容量的。
那么从这条边之前的点,可能引发出别的增广路径。
比如说 S -> b -> c -> d -> T 是一条增广路径,容量最小的边是 b -> c。
可能存在一条 S -> b -> e -> f -> g -> T 这样的增广路径。
这样的话,在找到第一条增广路径后,只需要回溯到 b 点,就可以继续找下去了。
这样做的好处是,避免了找到一条路径就从头开始寻找另外一条的开销。
也就是再次从 S 寻找到 b 的开销。
这个过程看似复杂,但是代码实现起来很优雅,因为它的本质就是回溯!


(3)
在同一次 DFS 中。如果从一个点引发不出任何的增广路径,就将这个点在层次图中抹去。

而这样一个算法,实现起来居然只需要100行。太吊了。
我的代码是参考别人的代码写的。可以用 POJ 1273 测试。

#include <stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
#include 
<limits.h>

#define MAX_VETXS 1024
#define MAX_EDGES 1024

int E[MAX_EDGES], next[MAX_EDGES], C[MAX_EDGES], M;
int V[MAX_VETXS], L[MAX_VETXS], Q[MAX_VETXS], N;
int S, T;

void __insert(int from, int to, int cap)
{
    M
++;
    C[M] 
= cap;
    E[M] 
= to;
    next[M] 
= V[from];
    V[from] 
= M;
}


void insert(int from, int to, int cap)
{
    __insert(from, to, cap);
    __insert(to, from, 
0);
}


int bfs()
{
    
int h, t, e, u, v;

    h 
= t = 0;
    Q[t
++= S;
    memset(L, 
0, N*sizeof(L[0]));
    L[S] 
= 1;
    
while (h != t) {
        u 
= Q[h++];
        
for (e = V[u]; e; e = next[e]) {
            v 
= E[e];
            
if (!L[v] && C[e] > 0{
                L[v] 
= L[u] + 1;
                Q[t
++= v;
            }

        }

    }


    
return L[T];
}


int dfs()
{
    
int t, u, v, e, i, f, r, back;

    t 
= 1;
    r 
= 0;

    
while (t) {
        u 
= (t == 1? S : E[Q[t - 1]];
        
if (u == T) {
            f 
= INT_MAX;
            
for (i = 1; i < t; i++{
                e 
= Q[i];
                
if (C[e] < f) {
                    f 
= C[e];
                    back 
= i;
                }

            }

            
for (i = 1; i < t; i++{
                e 
= Q[i];
                C[e] 
-= f;
                C[e
^1+= f;
            }

            r 
+= f;
            t 
= back;
        }
 else {
            
for (e = V[u]; e; e = next[e]) {
                v 
= E[e];
                
if (L[v] == L[u] + 1 && C[e] > 0)
                    
break;
            }

            
if (e)
                Q[t
++= e;
            
else {
                t
--;
                L[u] 
= 0;
            }

        }

    }


    
return r;
}


int dinic()
{
    
int f = 0;

    
while (bfs())
        f 
+= dfs();

    
return f;
}


int main()
{
    
int n, m, a, b, c, i;

    freopen(
"d:\\in.txt""r", stdin);

    
while (scanf("%d%d"&n, &m) != EOF) {
        S 
= 0;
        T 
= m - 1;
        N 
= m;
        memset(V, 
0, N*sizeof(V[0]));
        M 
= 2;
        
for (i = 0; i < n; i++{
            scanf(
"%d%d%d"&a, &b, &c);
            insert(a 
- 1, b - 1, c);
        }

        printf(
"%d\n", dinic());
    }


    
return 0;
}


posted on 2010-08-12 14:33 糯米 阅读(2489) 评论(4)  编辑 收藏 引用 所属分类: POJAlgorithm

评论

# re: Dinic 算法模板  回复  更多评论   

poj 3281 我之前用E-K bfs增广用了127ms
今天了解了dinic之后贴了你的这个模板,tle
这道题算是稀疏图吗,怎么dinic跑的这么惊人,求大牛讲解
2010-08-24 11:31 | slp

# re: Dinic 算法模板  回复  更多评论   

貌似有问题啊 向前星里面的V[]数组是为了获得边 从顶点转换成该顶点相连的边 LZ在DFS里面 入栈的是边 怎么循环里 又是e = V[u] u 是栈元素 不是边么? 求解???
2010-08-25 19:27 | TT

# re: Dinic 算法模板[未登录]  回复  更多评论   

@TT
u = (t == 1) ? S : E[Q[t - 1]];
这里 Q[t - 1] 是边
E[x] 是 x 这条有向边指向的顶点
2010-12-10 13:33 | 糯米

# re: Dinic 算法模板  回复  更多评论   

void __insert(int from, int to, int cap)
{
M++;
C[M] = cap;
E[M] = to;
next[M] = V[from];
V[from] = M;
}
应该改为
void __insert(int from, int to, int cap)
{
C[M] = cap;
E[M] = to;
next[M] = V[from];
V[from] = M;
M++;

}
2011-01-22 19:03 | .。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理