更高效的网络流算法
前言
填坑，介绍一种更高效的网络最大流算法HPLL（预留推进）
HPLL算法
在上一篇文章中，我们介绍了三种最大流算法：Edmonds-Karp、Dinic和ISAP，其中最优的复杂度为
思路
和ISAP类似，我们可以从汇点T开始BFS，查找到每一个结点的高度，然后每次搜索只更新到高度为当前节点减一的位置。这里HPLL引入了一个“溢出”节点的概念，可以理解为每个节点都有一个容量无限大的“水库”。当一个节点向下推流时，可以将流量先放在该节点的“水库”里。以便之后的搜索。
- 具体步骤：
- 1.BFS，记录每个节点的高度（和ISAP类似）
- 2.从源点S开始搜索，将“水库”中流量不为0的节点放入优先队列。
- 3.以从高到低的顺序更新队列里的每个节点，并将更新到的溢出节点放入优先队列。
- 4.若该节点无法再找到合法的路径（路径容量已满或者所有邻居节点都高于该节点）且该节点还有溢出流量，则将该点提升至邻居节点中高度最小的节点的高度加一处。
- 5.若发现某一高度出现断层，则说明其节点以上所有节点都无法再更新（具体证明可以看《算法导论》）。
- 不断重复3、4，直到所有节点都无法找到合法路径为止。Code
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
using namespace std;
const int N = 1300;
const int M = 240010;
const int inf = 0x3f3f3f3f;
int cnt = 1;
struct edge
{
int u, v, c, nxt;
edge(int u = 0, int v = 0, int c = 0, int nxt = 0) : u(u), v(v), c(c), nxt(nxt) {}
} e[M];
int n, m, s, t;
int head[N];
int flow[N]; // 记录节点的溢出流量。
inline int read()
{
int x = 0;
char c = getchar();
while (c > '9' || c < '0')
c = getchar();
while (c >= '0' && c <= '9')
x = x * 10 + c - '0', c = getchar();
return x;
}
void add_edge(int u, int v, int c)
{
cnt++;
e[cnt] = edge(u, v, c, head[u]);
head[u] = cnt;
}
int gap[M];
int dep[N];
bool isin[N]; // 记录节点是否在优先队列里
bool bfs(int s, int t)
{
bool *is;
is = new bool[N]();
for (int i = 1; i <= n; i++)
dep[i] = inf;
dep[t] = 0;
queue<int> q;
q.push(t);
is[t] = 1;
while (!q.empty())
{
int u = q.front();
is[u] = 0;
q.pop();
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
int c = e[i].c;
if (c || dep[v] <= dep[u] + 1)
continue;
dep[v] = dep[u] + 1;
if (is[v])
continue;
q.push(v);
is[v] = 1;
}
}
return dep[s] == inf;
}
struct cmp
{
bool operator()(int a, int b) const
{
return dep[a] < dep[b];
}
};
priority_queue<int, vector<int>, cmp> q; // 创建以深度大小排序的优先队列
void push(int u)
{
int nowflow = 0;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
int c = e[i].c;
if (!c || dep[v] + 1 != dep[u])
continue;
nowflow = min(c, flow[u]);
e[i].c -= nowflow;
e[i ^ 1].c += nowflow;
flow[u] -= nowflow;
flow[v] += nowflow;
if (!isin[v] && v != t && v != s)
{
q.push(v);
isin[v] = 1;
}
if (flow[u] == 0)
break;
}
}
void relabel(int u)
{ // 提升该节点
dep[u] = inf;
for (int i = head[u]; i; i = e[i].nxt)
{
if (!e[i].c)
continue;
dep[u] = min(dep[u], dep[e[i].v] + 1);
}
}
int maxflow(int s, int t)
{
if (bfs(s, t))
return 0;
dep[s] = n;
for (int i = 1; i <= n; i++)
if (dep[i] < inf)
gap[dep[i]]++;
for (int i = head[s]; i; i = e[i].nxt)
{ // 处理源点S
int v = e[i].v;
int nowflow = e[i].c;
if (nowflow)
{ // 将能流过的最大流量下传
flow[s] -= nowflow;
flow[v] += nowflow;
e[i].c -= nowflow;
e[i ^ 1].c += nowflow;
if (v != t && v != s && !isin[v])
{
q.push(v);
isin[v] = 1;
}
}
}
while (q.size())
{
int u = q.top(); // 每次从优先队列队首取节点，更新该节点的流量并推送到下一节点。
q.pop();
isin[u] = 0;
push(u);
if (flow[u])
{
gap[dep[u]]--;
if (!gap[dep[u]])
{ // 发现断层就说明该层以上所以节点都没有可以更新的增广路
for (int i = 1; i <= n; i++)
{
if (i != s && i != t && dep[i] > dep[u] && dep[i] < n + 1)
dep[i] = n + 1;
}
}
relabel(u);
gap[dep[u]]++;
q.push(u);
isin[u] = 1;
}
}
return flow[t];
}
signed main()
{
n = read();
m = read();
s = read();
t = read();
for (int i = 1; i <= m; i++)
{
int u, v, c;
u = read();
v = read();
c = read();
add_edge(u, v, c);
add_edge(v, u, 0);
}
cout << maxflow(s, t);
}后记
本篇文章比较简短，主要填上一篇文章的坑，若有任何错误或不清楚的地方，欢迎留言。 - 作者邮箱：2759094765@qq.com