|
|
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;
}
|