一种最大流数据生成方法

一种构造方法,仅 $532$ 个点,$24115$ 条边的图,使得 Dinic, SAP, ISAP 运行时间均大于 $1s$,
$1198$ 个点,$120796$ 条边运行时间均超过 $1 \mathrm{min}$(当然也可能是我的最大流写得太菜)

构造方法

maxFlowRevisited

如图所示,所有点被分成四个集合 $S, T, U, V$,$S, T$ 分别有 $k$ 个节点,$U, V$ 分别有 $2p$ 个节点($k, p$ 为定值)。

加粗的弧容量为 $1$,虚线容量为 $+\infty$,其他的弧容量为 $k$。

对于增广路算法,首先会花费 $O(k ^ 2)$ 的时间在 $\{s, S, T, t\}$ 中增广,长度为 $3$。
然后沿反向弧 ${T, S}$,在 $\{s, u_1, u_2, T, S, v_2, v_1, t\}$ 花费 $O(k ^ 2)$ 的时间,长度为 $7$。
然后在 $\{s, u_1, u_2, u_3, u_4, S, T, v_4, v_3, v_2, v_1, t\}$ 长度为 $11$,不停进行下去…

参数的选取

下面来确定 $k, p$ 的值,这个构造方法的点数为 $n = 2k + 4p + 2$,边数 $m = k ^ 2 + 2pk + 2k + 2p$,增广的数量为 $a = k ^ 2(p + 1)$。

令 $p = k - 1$,则 $n = 6k - 2, m = 3k ^ 2 + 4k - 4, a = k ^ 3$,即使会受到路径选择的影响,$a$ 也会是 $k ^ 3 / 216$ 的级别。

实现

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
#include <bits/stdc++.h>

struct Edge {
int u, v, w;
Edge(int u, int v, int w) : u(u), v(v), w(w) {}
};

// 6k - 2 顶点,3k ^ 2 + 4k - 4 边
inline void gen(int k) {
const int INF = 2147483647;
const int q = k - 1, n = 6 * k - 2;
const int src = 0, dst = 1;
int a = 2;
const int sb = a, se = (a += k);
const int tb = a, te = (a += k);
const int ub = a, ue = (a += 2 * q);
const int vb = a, ve = (a += 2 * q);
std::vector<Edge> edges;
for (int s = (sb); s < (se); s++) edges.push_back(Edge(src, s, k));
for (int t = (tb); t < (te); t++) edges.push_back(Edge(t, dst, k));
for (int s = (sb); s < (se); s++)
for (int t = (tb); t < (te); t++) edges.push_back(Edge(s, t, 1));
edges.push_back(Edge(src, ub, INF));
edges.push_back(Edge(vb, dst, INF));
for (int u = (ub); u < (ue - 1); u++) edges.push_back(Edge(u, u + 1, INF));
for (int v = (vb); v < (ve - 1); v++) edges.push_back(Edge(v + 1, v, INF));
for (int u = ub + 1; u < ue; u += 4)
for (int t = (tb); t < (te); t++) edges.push_back(Edge(u, t, k));
for (int u = ub + 3; u < ue; u += 4)
for (int s = (sb); s < (se); s++) edges.push_back(Edge(u, s, k));
for (int v = vb + 1; v < ve; v += 4)
for (int s = (sb); s < (se); s++) edges.push_back(Edge(s, v, k));
for (int v = vb + 3; v < ve; v += 4)
for (int t = (tb); t < (te); t++) edges.push_back(Edge(t, v, k));
std::cout << n << ' ' << edges.size() << ' ' << src + 1 << ' ' << dst + 1
<< '\n';
srand(clock() * time(0));
std::random_shuffle(edges.begin(), edges.end());
for (int i = 0; i < (int)edges.size(); i++) {
std::cout << edges[i].u + 1 << ' ' << edges[i].v + 1 << ' '
<< edges[i].w << '\n';
}
}

int main(const int argc, const char *argv[]) {
if (argc < 2) {
std::cerr << "invalid input!!!";
return 0;
}
int k = atoi(argv[1]);
gen(k);
return 0;
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×