Chenfan Blog

Do cool things that matter.

0%

网络流整理

Posted on Edited on In

今天来整理一下网络流的相关内容。

首先贴一个博客：网络流(Network Flow)

关于网络流的介绍，这里都讲得比较详细了。

然后是模板题：HDU 3549

Flow Problem

Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)

Problem Description

Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.

Input

The first line of input contains an integer T, denoting the number of test cases.

For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000)

Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000)

Output

For each test cases, you should output the maximum flow from source 1 to sink N.

Sample Input

2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1

Sample Output

Case 1: 1
Case 2: 2

算法模板

最基础的Edmonds-Karp（EK）算法

每一次运行都是从源点到汇点，广搜找一遍增广路。如果能够找到，则反向推回去把流加上去，直到找不到任何其他增广路为止，则结束。

复杂度是$O(V*E^2)$

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/* ***********************************************
MYID	: Chen Fan
LANG	: G++
PROG	: 3549_EK
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int start[100],num[100];

typedef struct nod {
	int x,y;
} node;
node edge[3000];

bool op(node a,node b)
{
	if (a.x==b.x) return a.y<b.y;
	else return a.x<b.x;
}

int c[100][100];

int tail,front[100],minn,next;

bool find(int n)
{
	queue<int> q;
	bool flag[100];
	memset(flag,0,sizeof(flag));
	int outp[100];

	q.push(1);
	front[1]=0;
	outp[1]=2147483647;
	flag[1]=true;
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		for (int i=0;i<num[now];i++)
		{
			int next=edge[start[now]+i].y;
			if (!flag[next]&&c[now][next]>0)
			{
				flag[next]=true;
				q.push(next);
				front[next]=now;
				outp[next]=min(outp[now],c[now][next]);
				if (next==n)
				{
					minn=outp[next];
					return true;
				}
			}
		}
	}
	return false;
}

int main()
{
	int t;
	scanf("%d",&t);

	for (int tt=1;tt<=t;tt++)
	{
		int n,m;
		scanf("%d%d",&n,&m);

		memset(c,0,sizeof(c));
		tail=0;
		for (int i=1;i<=m;i++)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			if (!(c[x][y]||c[y][x]))
			{
				tail++;
				edge[tail].x=x;
				edge[tail].y=y;
				tail++;
				edge[tail].x=y;
				edge[tail].y=x;
			}
			c[x][y]+=z;
		}

		memset(num,0,sizeof(num));
		int o=0;
		sort(&edge[1],&edge[1+tail],op);
		for (int i=1;i<=tail;i++)
		{
			if (o!=edge[i].x)
			{
				o=edge[i].x;
				start[o]=i;
			}
			num[o]++;
		}

		int ans=0;
		while (find(n))
		{
			int i=n,j=front[n];
			while(j)
			{
				c[j][i]-=minn;
				c[i][j]+=minn;
				i=j;
				j=front[i];
			}
			ans+=minn;
		}

		printf("Case %d: %d\n",tt,ans);
	}

	return 0;
}

ISAP算法

引用一下 网络流ISAP算法的简单介绍（zz）

众所周知，在网络流的世界里，存在2类截然不同的求解思想，就是比较著名的预流推进与增广路，两者都需要反向边的小技巧。

其中预流推进的算法思想是以边为单元进行推流操作。具体流程如下:置初始点邻接边满流并用一次反向bfs对每个结点计算反向距离标号，定义除汇点外存量大于出量的结点为活动结点，每次对活动结点按允许边（u->v:d[u]=d[v]+1）进行推流操作，直到无法推流或者该点存量为0，若u点此时仍为活动结点，则进行重标号，使之等于原图中进行推操作后的邻接结点的最小标号+1，并将u点入队。当队列为空时，算法结束，只有s点和t点存量非0，网络中各顶点无存量，无法找到增广路继续增广，则t点存量为最大流。

而增广路的思想在于每次从源点搜索出一条前往汇点的增广路，并改变路上的边权，直到无法再进行增广，此时汇点的增广量即为最大流。两者最后的理论基础依然是增广路定理，而在理论复杂度上预流推进要显得比较优秀。其中的HLPP高标预流推进的理论复杂度已经达到了另人发指的$O（\sqrt{m}*n^2）$，但是其编程复杂度也是同样的令人发指

于是我们能否在编程复杂度和算法复杂度上找到一个平衡呢，答案是肯定的。我们使用增广路的思想，而且必须进行优化。因为原始的增广路算法（例如EK）是非常悲剧的。于是有人注意到了预流推进中的标号法，在增广路算法中引入允许弧概念，每次反搜残留网络得到结点标号，在正向增广中利用递归进行连续增广，于是产生了基于分层图的Dinic算法。一些人更不满足于常规Dinic所带来的提升，进而加入了多路分流增广的概念，即对同一顶点的流量，分多路同时推进，再加上比较复杂的手工递归，使得Dinic已经满足大部分题目的需要。

然而这样做就是增广路算法优化的极限么？答案永远是不。人们在Dinic中只类比了预流推进的标号技术，而重标号操作却没有发挥得淋漓尽致。于是人们在Dinic的基础上重新引入了重标号的概念，使得算法无须在每次增广后再进行BFS每个顶点进行距离标号，这种主动标号技术使得修正后算法的速度有了不少提高。但这点提高是不足称道的，人们又发现当某个标号的值没有对应的顶点后，即增广路被截断了，于是算法便可以提前结束，这种启发式的优化称为Gap优化。最后人们结合了连续增广，分层图，多路增广，Gap优化，主动标号等穷凶极恶的优化，更甚者在此之上狂搞个手动递归，于是产生了增广路算法的高效算法–ISAP算法。

虽然ISAP算法的理论复杂度仍然不可超越高标预流推进，但其编程复杂度已经简化到发指，如此优化，加上不逊于Dinic的速率（在效率上手工Dinic有时甚至不如递归ISAP），我们没有不选择它的理由。

ISAP是将SAP的预处理广搜得到标号优化进了整个过程中，代码更简洁，而效率也是更快了。

以下还是上面这题的ISAP解法：

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/* ***********************************************
MYID	: Chen Fan
LANG	: G++
PROG	: 3549_ISAP
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int start[100],num[100];

typedef struct nod {
	int x,y;
} node;
node edge[3000];

bool op(node a,node b)
{
	if (a.x==b.x) return a.y<b.y;
	else return a.x<b.x;
}

int c[100][100];

int tail,front[100],minn,next,gap[100],h[100],n;

int dfs(int now,int flow)
{
	if (now==n)
	{
		return flow;
	}

	int minh=n-1,lv=flow,d;

	for (int j=0;j<num[now];j++)
	{
		int next=edge[start[now]+j].y;
		if (c[now][next]>0)
		{
			if (h[next]+1==h[now])
			{
				d=min(lv,c[now][next]);

				d=dfs(next,d);

				c[now][next]-=d;
				c[next][now]+=d;

				lv-=d;
				if (h[1]>=n) return flow-lv;
				if (lv==0) break;
			}

			if (minh>h[next]) minh=h[next];
		}
	}

	if (lv==flow)
	{
		gap[h[now]]--;
		if (!gap[h[now]]) h[1]=n;
		h[now]=minh+1;
		gap[h[now]]++;
	}

	return flow-lv;
}

int main()
{
	int t;
	scanf("%d",&t);

	for (int tt=1;tt<=t;tt++)
	{
		int m;
		scanf("%d%d",&n,&m);

		memset(c,0,sizeof(c));
		tail=0;
		for (int i=1;i<=m;i++)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			if (!(c[x][y]||c[y][x]))
			{
				tail++;
				edge[tail].x=x;
				edge[tail].y=y;
				tail++;
				edge[tail].x=y;
				edge[tail].y=x;
			}
			c[x][y]+=z;
		}

		memset(num,0,sizeof(num));
		int o=0;
		sort(&edge[1],&edge[1+tail],op);
		for (int i=1;i<=tail;i++)
		{
			if (o!=edge[i].x)
			{
				o=edge[i].x;
				start[o]=i;
			}
			num[o]++;
		}

		int ans=0;

		memset(gap,0,sizeof(gap));
		memset(h,0,sizeof(h));

		gap[1]=n;

		while (h[1]<n)
		{
			ans+=dfs(1,2147483647);
		}

		printf("Case %d: %d\n",tt,ans);
	}

	return 0;
}