最近研究了一下网络流.最常见的几个算法有下边几种
一:增广路算法
在残余网络中不断的找增广路

  1. Ford-Fulkerson

    2. 很不幸,这是一个用dfs找任意增广路的算法.时间复杂度无从估计

  2. Edmonds-Karp

    3. 用bfs代替了dfs寻找增广路,悲观的时间复杂度是O(VE2)

  3. Dinic

    4. 据说和SAP很像,还没研究,O(V2E)

  4. Shortest Augmenting Paths(也就是很流行的SAP算法)

    5. 故名思议,就是找最短的增广路,把EK算法的O(E)时间优化到了O(V),故复杂度为O(V2E)
    不过加了间隙优化后效率和Dinic不可同日而语

二:预留推进算法
非常形象的灌水机制,一开始源点在最高,向各个管道灌水,如果一个点有盈余,那么它必需往低处流(Push),不能留的话上升高度(Relabel)后再往低处流

  1. Push_Relabel

    2. 很朴实的预留推进算法,O(V4)

  2. Relabel_to_Front

    3. 用一个List维护各个点,当一个点被relabel后回到List首部(to front)再往后计算,O(V3)

  3. Highest_Relabel(不知道这是不是传说中的HLPP算法–Highest_Label_Preflow_PushO(V2E1/2))

    4. Relabel_to_Front的改进版,List分层从最高的点开始流,并且加上BFS预处理和间隙优化后效率会有不可思议的提高

据说还有一些复杂度非常奇怪的算法:VElogE/(V/logV)(V)、min(V2/3,E1/2)Elg(V2/E+2)lgC…..

用PKU的1459 Power Network(多源多汇的模板题)来测模版,比较如下

  • Edmonds_Karp.313MS
    • ?View Code CPP
    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

    #define M 222
int maze[M][M];
int pre[M];
int q[M],head,tail;
 
int EK(int s,int t,int nodenum) {
	int maxflow = 0;
	while(true) {
		CC(pre,-1);
		q[head = tail = 0] = s;
		while(head <= tail) {
			int u = q[head++];
			FF(v,nodenum) if(pre[v] == -1 && maze[u][v]) {
				pre[v] = u;
				q[++tail] = v;
			}
			if(pre[t] != -1)	break;
		}
		if(pre[t] == -1)	break;
		int aug = -1;
		for(int v = t , u = pre[v] ; v != s ; v = u , u = pre[u]) {
			checkmin(aug,maze[u][v]);
		}
		for(int v = t , u = pre[v] ; v != s ; v = u , u = pre[u]) {
			maze[u][v] -= aug;
			maze[v][u] += aug;
		}
		maxflow += aug;
	}
	return maxflow;
}
  • SAP+GAP优化(间隙优化)63MS
    • ?View Code CPP
    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

    #define M 666
int maze[M][M];
int gap[M],dis[M],pre[M],cur[M];
int s,t,n;
int sap() {
	CC(cur,0);CC(dis,0);CC(gap,0);
	int u = pre[s] = s,maxflow = 0,aug = -1;
	gap[0] = n;
	while(dis[s] < n) {
loop:
		FOR(v,cur[u],n) if(maze[u][v] && dis[u] == dis[v] + 1) {
			cur[u] = v;
			checkmin(aug,maze[u][v]);
			pre[v] = u;
			u = v;
			if(v == t) {
				maxflow += aug;
				for(u = pre[u];v != s;v = u,u = pre[u]) maze[u][v] -= aug,maze[v][u] += aug;
				aug = -1;
			}
			goto loop;
		}
		int mind = n;
		FF(v,n) if(maze[u][v] && (mind > dis[v])) {
			cur[u] = v;
			mind = dis[v];
		}
		if((--gap[dis[u]])== 0)    break;
		gap[dis[u] = mind+1] ++;
		u = pre[u];
	}
	return maxflow;
}
  • Push_Relabel 79MS
    • ?View Code CPP
    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

    #define M 222
int maze[M][M];
int e[M];
int h[M];
queue <int> q;
bool Inq[M];
int n , m ;
int s , t ;
 
void Init_Preflow() {
	CC(e,0);
	CC(h,0);
	CC(Inq,false);
	h[s] = n;
	FF(i,n) {
		if(maze[s][i] && i != s) {
			e[i] += maze[s][i];
			maze[i][s] = maze[s][i];
			e[s] -= maze[s][i];
			maze[s][i] = 0;
			if(e[i] && i != t) {
				Inq[i] = true;
				q.push(i);
			}
		}
	}
}
 
void Push(int u) {
	int minh = -1 , x = -1;
	FF(v,n) {
		if(maze[u][v]) {
			if(h[u] == h[v] + 1) {
				x = min(e[u],maze[u][v]);
				maze[u][v] -= x;
				e[u] -= x;
				maze[v][u] += x;
				e[v] += x;
				if(!Inq[v] && v != s && v != t) {
					Inq[v] = true;
					q.push(v);
				}
				if(e[u] == 0) {
					return ;
				}
			} else {
				checkmin(minh,h[v]);
			}
		}
	}
	h[u] = minh + 1;
	Push(u);
}
 
int Push_Relabel() {
	Init_Preflow();
	while(!q.empty()) {
		int u = q.front();
		Push(u);
		q.pop();
		Inq[u] = false;
	}
	return e[t];
}
  • Relabel_to_Front 141ms(一定是我写挫了..理论上比Push_Relabel快一个级别的竟然这么慢)
    • ?View Code CPP
    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

    #define M 222
int maze[M][M];
int e[M];
int h[M];
int cur[M];
struct List{
	int next;
	int pos;
}L[M];
int len;
int n , m ;
int s , t ;
 
void Init() {
	CC(e,0);
	CC(h,0);
	h[s] = n;
	FF(v,n) {
		e[v] += maze[s][v];
		e[s] -= maze[s][v];
		maze[v][s] += maze[s][v];
		maze[s][v] = 0;
	}
	L[0].next = -1;
	len = 1;
	CC(cur,0);
	FF(v,n) {//将不是s和t的节点推进列表里
		if(v != s && v != t) {
			L[len].next = L[0].next;
			L[len].pos = v;
			L[0].next = len++;
		}
	}
}
 
void Check(int u) {
	int &v = cur[u];
	while(e[u]) {
		if(v == n) {//全部检查完还有盈余,那么改变高度
			int minh = -1;
			FF(v,n) {
				if(maze[u][v]) {
					checkmin(minh,h[v]);
				}
			}
			h[u] = minh + 1;
			v = 0;//重新检查
		} else {
			if(maze[u][v] && h[u] == h[v] + 1) {//找到可行弧,push
				int x = min(e[u],maze[u][v]);
				e[u] -= x;
				maze[u][v] -= x;
				e[v] += x;
				maze[v][u] += x;
			} else {
				v ++;
			}
		}
	}
}
 
int Relabel_to_Front() {
	Init();
	int now = L[0].next;
	int fa = 0;
	while(now != -1) {
		int &u = L[now].pos;
		int high = h[u];
		Check(u);
		if(h[u] != high) {//如果高度变化过,将now插到列表最前
			L[fa].next = L[now].next;
			L[now].next = L[0].next;
			L[0].next = now;
		}
		fa = now;
		now = L[now].next;
	}
	return e[t];
}
  • Highest_Relabel 63ms(写的很挫,写的很烂,随便加了gap优化.日后改进)
    • ?View Code CPP
    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

    #define M 222
int maze[M][M];
int e[M];
int h[M];
int cur[M];
struct List{
	int next;
	int pos;
}L[M*4];
int len;
int n , m ;
int s , t ;
struct Q{
	int pos;
	int tep;
};
queue <Q> q;
vector <int> edge[M];
int gap[M*2];
 
void Init() {
	CC(e,0);
	FF(v,n) {
		e[v] += maze[s][v];
		e[s] -= maze[s][v];
		maze[v][s] += maze[s][v];
		maze[s][v] = 0;
	}
	//L列表处理
	CC(h,0);
	FF(i,2*n) {
		L[i].next = -1;
	}
	len = 2*n;
	h[s] = n;
	FF(v,n) {//将不是s和t的且在s和t之间之间节点推进列表里
		if(v != s && v != t) {
			L[len].next = L[0].next;
			L[len].pos = v;
			L[0].next = len++;
		}
	}
	CC(cur,0);
	CC(gap,0);
	gap[0] = n;
}
 
void Check(int u) {
	int &v = cur[u];
	while(e[u]) {
		if(v == n) {//全部检查完还有盈余,那么改变高度
			int minh = -1;
			FF(v,n) {
				if(maze[u][v]) {
					checkmin(minh,h[v]);
				}
			}
			h[u] = minh + 1;
			v = 0;//重新检查
		} else {
			if(maze[u][v] && h[u] == h[v] + 1) {//找到可行弧,push
				int x = min(e[u],maze[u][v]);
				e[u] -= x;
				maze[u][v] -= x;
				e[v] += x;
				maze[v][u] += x;
			} else {
				v ++;
			}
		}
	}
}
 
int Highest_Relabel() {
	Init();
	int level = 0;
	int flag = -1;
	while(level >= 0) {
		int now = L[level].next;
		int fa = level--;
		while(now != -1) {
			int &u = L[now].pos;
			int high = h[u];
			Check(u);
			if(h[u] != high) {//如果高度变化过,将now插到列表最前
				gap[high] --;
				if(gap[high] == 0) {
					flag = high;
				}
				gap[h[u]] ++;
				L[fa].next = L[now].next;
				level = h[u];
				L[now].next = L[level].next;
				L[level].next = now;
				if(flag != -1) {
					checkmin(level,flag);
				}
				break;
			}
			fa = now;
			now = L[now].next;
		}
	}
	return e[t];
}

考虑到编程复杂度,最终我臣服在sap下…而且询问过很多大牛,基本没有题目能卡sap的.
于是以后我所用的模板就锁定以下两个
矩阵:

?View Code CPP
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

#define M 1000
int maze[M][M];
int gap[M],dis[M],pre[M],cur[M];
int sap(int s,int t,int nodenum) {
	CC(cur,0);CC(dis,0);CC(gap,0);
	int u = pre[s] = s,maxflow = 0,aug = -1;
	gap[0] = nodenum;
	while(dis[s] < nodenum) {
loop:		FOR(v,cur[u],nodenum) if(maze[u][v] && dis[u] == dis[v] + 1) {
			checkmin(aug,maze[u][v]);
			pre[v] = u;
			u = cur[u] = v;
			if(v == t) {
				maxflow += aug;
				for(u = pre[u];v != s;v = u,u = pre[u]) {
					maze[u][v] -= aug;
					maze[v][u] += aug;
				}
				aug = -1;
			}
			goto loop;
		}
		int mindis= nodenum-1;
		FF(v,nodenum) if(maze[u][v] && mindis> dis[v]) {
			cur[u] = v;
			mindis= dis[v];
		}
		if((--gap[dis[u]])== 0)    break;
		gap[dis[u] = mindis+1] ++;
		u = pre[u];
	}
	return maxflow;
}

静态邻接表:

?View Code CPP
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

#define M 40010
int gap[M],dis[M],pre[M],cur[M];
int NE,NV;
int head[M];
struct Node{
	int c,pos,next;
}E[999999];
int sap(int s,int t) {
	memset(dis,0,sizeof(int)*(NV+1));
	memset(gap,0,sizeof(int)*(NV+1));
	FF(i,NV) cur[i] = head[i];
	int u = pre[s] = s,maxflow = 0,aug = -1;
	gap[0] = NV;
	while(dis[s] < NV) {
loop:		for(int &i = cur[u]; i != -1; i = E[i].next) {
			int v = E[i].pos;
			if(E[i].c && dis[u] == dis[v] + 1) {
				checkmin(aug,E[i].c);
				pre[v] = u;
				u = v;
				if(v == t) {
					maxflow += aug;
					for(u = pre[u];v != s;v = u,u = pre[u]) {
						E[cur[u]].c -= aug;
						E[cur[u]^1].c += aug;
					}
					aug = -1;
				}
				goto loop;
			}
		}
		int mindis = NV;
		for(int i = head[u]; i != -1 ; i = E[i].next) {
			int v = E[i].pos;
			if(E[i].c && mindis > dis[v]) {
				cur[u] = i;
				mindis = dis[v];
			}
		}
		if( (--gap[dis[u]]) == 0)    break;
		gap[ dis[u] = mindis+1 ] ++;
		u = pre[u];
	}
	return maxflow;
}
void Insert(int u,int v,int c,int cc = 0) {
	E[NE].c = c;	E[NE].pos = v;
	E[NE].next = head[u];	head[u] = NE++;
	E[NE].c = cc;	E[NE].pos = u;
	E[NE].next = head[v];	head[v] = NE++;
}
 
int main() {
	FF(i,NV) head[i] = -1;
	NE = 0;
}

至于其他模板,特别是预留推进的,写的非常糟糕..甚至还有很多漏洞,编译器不同还产生不懂的结果- -(虽然能过上边PKU那题),于是这几个模板没能派上用场便胎死腹中

我对一个算法的复杂度考虑只停留在数几个for循环,对于这么复杂的需要递归的算法,向来不知道该如何计算,只能参考一些资料
主要研究《网络流算法介绍与分析》,几乎所有代码都是根据这上边的理论扯出来的

Popularity: 22% [?]