实现技巧整理

  • 关于回滚操作的技巧在需要回滚的数组比较多的时候一个一个开栈回滚会比较麻烦,可以试着下面这样写:

    1
    2
    3
    int *sta_p[maxn*k], sta_v[maxn*k], top;

    void modify(int &x) {++ top; sta_p[top] = &x; sta_v[top] = x;}

    这样还原的时候也只需要根据指针搞一搞就好,只需要开一个栈就行了,注意 \(k\) 不要开小。

  • 有时候你需要记录一个支持随时清空的 \(01\) 数组,这时可以不额外开标记数组。记一个变量 \(tim\),赋 \(1\) 的时候就设为 \(tim\),判断是 \(0\) 还是 \(1\) 就看是否等于 \(tim\),清空就 \(tim \leftarrow tim + 1\)

  • 上下界费用流,对每条必须边不要直接添加,而是对每一个点记一个度数,全部添加之后再根据度数决定每个点到超级源还是超级汇,连多大流量的边,这样可以大大减少边数。

  • 在做 dinic 时以下两份代码有巨大常数差距,下面的有时甚至可以比上面的快十倍,不知道为什么。

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
int _find(int u, int in) {
if (u == cur_sink) return in;
int w = 0, t;
for (int &p = cur[u]; p >= 0 && w < in; p = E[p].x) {
if (p >= e) continue;
if (E[p].c && L[E[p].v] == L[u] + 1) {
if ((t = _find(E[p].v, min(E[p].c, in - w)))) {
w += t;
E[p].c -= t;
E[p^1].c += t;
}
}
}
if (w < in) L[u] = -1;
return w;
}

int _find(int u, int in) {
if (u == cur_sink) return in;
int w = 0, t;
for (int &p = cur[u]; p >= 0; p = E[p].x) {
if (p >= e) continue;
if (E[p].c && L[E[p].v] == L[u] + 1) {
if ((t = _find(E[p].v, min(E[p].c, in - w)))) {
w += t;
E[p].c -= t;
E[p^1].c += t;
if (w == in) break;
}
}
}
if (w < in) L[u] = -1;
return w;
}