「BZOJ 4519」不同的最小割-GomoryHuTree

给出一个无向连通图,求所有点对的最小割数值中不同的个数。

链接

BZOJ 4519

题解

GomoryHu Tree,方式就是先把除 $1$ 号点外的的点的父亲置为 $1$,然后每次取出其中一个点 $u$ 和它的父亲 $v$ 计算最小割,然后 bfs 残量网络,若满流且其父亲为 $v$,则把这个点的父亲置为 $u$。

由于两点的最小割在 GomoryHu Tree 上是路径的最小值,所以直接求出建树过程中计算的最小割的数值种数即可。

时间复杂度 $O(n \cdot \mathrm{maxflow}(n, m))$。

代码

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
/**
* Copyright (c) 2016-2018, xehoth
* All rights reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
* http://www.apache.org/licenses/LICENSE-2.0
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
* 「BZOJ 4519」不同的最小割 19-03-2018
* GomoryHuTree
* @author xehoth
*/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
struct InputStream {
enum { SIZE = 1024 * 1024 };
char ibuf[SIZE], *s;
InputStream() : s(ibuf) { fread(s, 1, SIZE, stdin); }
inline InputStream &operator>>(int &x) {
while (!isdigit(*s)) s++;
for (x = 0; isdigit(*s); s++) x = x * 10 + (*s ^ '0');
return *this;
}
} io;
const int MAXN = 850 + 9;
const int INF = 0x3f3f3f3f;
struct Maxflow {
struct Node {
int v, f, c, i;
Node(int v, int f, int i) : v(v), f(f), c(f), i(i) {}
};
std::vector<Node> g[MAXN];
inline void addEdge(int u, int v, int f) {
g[u].push_back(Node(v, f, g[v].size()));
g[v].push_back(Node(u, f, g[u].size() - 1));
}
typedef std::vector<Node>::iterator Iterator;
int n, s, t, iter[MAXN], h[MAXN], gap[MAXN];
int dfs(int u, int flow) {
if (u == t) return flow;
int ret = 0;
for (int &i = iter[u]; i < (int)g[u].size(); i++) {
Node &p = g[u][i];
if (p.f > 0 && h[u] == h[p.v] + 1) {
int df = dfs(p.v, std::min(flow - ret, p.f));
p.f -= df;
g[p.v][p.i].f += df;
if ((ret += df) == flow || h[s] >= n) return ret;
}
}
if (--gap[h[u]] == 0) h[s] = n;
gap[++h[u]]++;
iter[u] = 0;
return ret;
}
inline int maxflow(int s, int t) {
this->s = s;
this->t = t;
memset(gap, 0, sizeof(int) * (n + 1));
memset(h, 0, sizeof(int) * (n + 1));
int ret = 0;
for (gap[0] = n; h[s] < n;) {
memset(iter, 0, sizeof(int) * (n + 1));
ret += dfs(s, INF);
}
return ret;
}
inline void reset() {
for (int i = 0; i <= n; i++)
for (Iterator p = g[i].begin(); p != g[i].end(); ++p) p->f = p->c;
}
inline std::vector<Node> &operator[](int i) { return g[i]; }
inline const std::vector<Node> &operator[](int i) const { return g[i]; }
} g;
struct GomoryHuTree {
int fa[MAXN], flow[MAXN];
bool vis[MAXN];
inline bool bfs(Maxflow &g) {
memset(vis, 0, sizeof(bool) * (g.n + 1));
std::queue<int> q;
q.push(g.s);
vis[g.s] = true;
for (int u; !q.empty();) {
u = q.front();
q.pop();
for (Maxflow::Iterator p = g[u].begin(); p != g[u].end(); ++p) {
if (p->f && !vis[p->v]) {
vis[p->v] = true;
q.push(p->v);
}
}
}
}
inline void build(Maxflow &g) {
for (int i = 2; i <= g.n; i++) fa[i] = 1;
for (int u = 2, v; u <= g.n; u++) {
v = fa[u];
flow[u - 1] = g.maxflow(u, v);
bfs(g);
for (int i = u + 1; i <= g.n; i++)
if (fa[i] == v && vis[i]) fa[i] = u;
g.reset();
}
}
} d;
int main() {
int n, m;
io >> n >> m;
g.n = n;
for (int i = 0, u, v, f; i < m; i++) {
io >> u >> v >> f;
g.addEdge(u, v, f);
}
d.build(g);
std::sort(d.flow + 1, d.flow + n);
std::cout << std::unique(d.flow + 1, d.flow + n) - d.flow - 1;
return 0;
}
分享到