先来回顾一下 dinic\textbf{dinic} 算法执行多路增广的过程
流 ∣f∣|f| 是最大可行流的条件是，当且仅当 GfG_f 中 S⇝TS \rightsquigarrow T 一条增广路径都没有
augment

拆点

takeapart

有向图的不相交路径

最大流可以解决的一种重要的模型，可以简单描述为
有向图中有多少条不相交的路径？
具体描述为
在有向图中能够取出多少条，没有公共点的，长度为 LL 的路径？

Acwing2180
Acwing2180

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
const int maxn = 1010, maxm = (250000 + 10) * 2;
const int inf = 0x3f3f3f3f;

int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
int A[maxn], L = 0, n, S, T;
void add(int a, int b, int c) {
    ver[++idx] = b; e[idx] = c; ne[idx] = head[a]; head[a] = idx;
    ver[++idx] = a; e[idx] = 0; ne[idx] = head[b]; head[b] = idx;
}

int g[maxn];
void dp() {
    L = 0;
    for (int i = 1; i <= n; i++) {
        g[i] = 1;
        for (int j = 1; j < i; j++) {
            if (A[j] <= A[i]) g[i] = max(g[i], g[j] + 1);
        }
        L = max(L, g[i]);
    }
}

int d[maxn], cur[maxn];
bool bfs() {
    memset(d, -1, sizeof d);
    d[S] = 0, cur[S] = head[S];
    queue<int> q; q.push(S);

    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (d[y] == -1 && e[i]) {
                d[y] = d[x] + 1;
                cur[y] = head[y];
                if (y == T) return true;
                q.push(y);
            }
        }
    }
    return false;
}

int dinic(int u, int lim) {
    if (u == T) return lim;
    int flow = 0;
    for (int i = cur[u]; i && lim > flow; i = ne[i]) {
        cur[u] = i;
        int v = ver[i];
        if (d[v] == d[u] + 1 && e[i]) {
            int t = dinic(v, min(e[i], lim - flow));
            if (!t) d[v] = -1;
            flow += t, e[i] -= t, e[i^1] += t;
        }
    }
    return flow;
}

int dinic() {
    int res = 0, flow;
    while (bfs()) while (flow = dinic(S, inf)) res += flow;
    return res;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
    S = 0, T = 2*n + 2;

    // dp
    dp();
    printf("%d\n", L);

    if (L == 1) {
        printf("%d\n%d\n", n, n);
        return 0;
    }

    // build graph
    for (int i = 1; i <= n; i++) {
        add(i, n+i, 1);
        if (g[i] == 1) add(S, i, 1);
        if (g[i] == L) add(n+i, T, 1);

        for (int j = 1; j < i; j++) {
            if (A[j] <= A[i] && g[i] == g[j] + 1) add(n+j, i, 1);
        }
    }

    // solve
    int res = dinic();
    printf("%d\n", res);
    for (int i = 2; i <= idx; i++) {
        int a = ver[i^1], b = ver[i];
        if (a == S && b == 1) e[i] = inf;
        if (a == 1 && b == n+1) e[i] = inf;
        if (a == n+n && b == T) e[i] = inf;
        if (a == n && b == n+n) e[i] = inf;
    }
    res += dinic();
    printf("%d\n", res);
}

源汇不确定时还原现场

有时候最大流问题需要我们枚举源点和汇点
此时每次枚举完毕的时候，要还原现场

  • 对于边 e∈E[⋯idx]e \in E[\cdots \text{idx}]，e[i]e[i] 的流量 ∣f∣|f| 为 e[i⊕1]e[i \oplus 1] 的容量 ∣c∣|c|
  • dinic\text{dinic} 算法维护的是残量网络 GfG_f，最开始流量为 00

所以还原现场 22 步即可，注意残量网络中 e=c(u,v)e = c(u, v)，边维护的是容量
对于所有的边 for ∀ei∈E[⋯idx]\textbf{for} \ \forall e_i \in E[\cdots \text{idx}]

  • 反向边容量退流，e[i]←e[i]+e[i⊕1]e[i] \leftarrow e[i] + e[i \oplus 1]
  • 正向边流量清空，正向边流量等于反向边容量，所以 e[i⊕1]←0e[i \oplus 1] \leftarrow 0

Acwing2278

  • 对于冰块 uu，它的每一条出边 ii，必须满足 ∑ei⩽mu\sum e_i \leqslant m_u
    很自然地想到拆点，u→(u1,u2),e(u1,u2)=muu \to (u_1, u_2), \quad e(u_1, u_2) = m_u
  • 冰块 (u,v)(u, v) 之间能够互相跳到，充要条件是 dist(u,v)⩽D\text{dist}(u, v) \leqslant D
    由于 (u,v)(u, v) 这条路径上可以允许无数企鹅经过
    （注意，对起跳终点 vv 并没有限制，对起点的限制已经加在拆点上了）
    添加边 c(u,v)=∞, c(v,u)=∞,u,vc(u, v) = \infty, \ c(v, u) = \infty, \quad u, v 是拆点后的
  • 考虑源点，对于所有有企鹅的冰块，for ∀i,ni>0\textbf{for} \ \forall i, \quad n_i > 0:
    c(S,i)=nic(S, i) = n_i
  • 枚举每一个汇点 T∈[1⋯n]T \in [1 \cdots n]，枚举前记得还原现场，如果
    dinic(S,T)=tot,res++\textbf{dinic}(S, T) = tot, \quad res ++
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
typedef pair<int, int> PII;
const int maxn = 210, maxm = (210 + 210 + 210*210) * 2;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;

int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
int n, S = 0, T, tot = 0;
double D;
PII ice[maxn];

void add(int a, int b, int c) {
    ver[++idx] = b; e[idx] = c; ne[idx] = head[a]; head[a] = idx;
    ver[++idx] = a; e[idx] = 0; ne[idx] = head[b]; head[b] = idx;
}

bool check(const PII &a, const PII &b) {
    double dx = a.first - b.first, dy = a.second - b.second;
    return dx*dx + dy*dy <= D*D + eps;
}

void init() {
    memset(head, 0, sizeof head);
    idx = 1;
    tot = 0;
}

int d[maxn], cur[maxn];
bool bfs() {
    memset(d, -1, sizeof d);
    d[S] = 0, cur[S] = head[S];
    queue<int> q; q.push(S);
    while (q.size()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i];
            if (d[y] == -1 && e[i]) {
                d[y] = d[x] + 1;
                cur[y] = head[y];
                if (y == T) return true;
                q.push(y);
            }
        }
    }
    return false;
}

int dinic(int u, int lim) {
    if (u == T) return lim;
    int flow = 0;
    for (int i = cur[u]; i && lim > flow; i = ne[i]) {
        cur[u] = i;
        int v = ver[i];
        if (d[v] == d[u] + 1 && e[i]) {
            int t = dinic(v, min(e[i], lim - flow));
            if (!t) d[v] = -1;
            flow += t, e[i] -= t, e[i^1] += t;
        }
    }
    return flow;
}

int dinic() {
    int res = 0, flow;
    while (bfs()) while (flow = dinic(S, inf)) res += flow;
    return res;
}

void solve() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        T = i;
        for (int k = 2; k <= idx; k += 2) {
            e[k] += e[k^1];
            e[k^1] = 0;
        }
        int res = dinic();
        if (res == tot) {
            cnt++;
            printf("%d ", i-1);
        }
    }
    if (cnt == 0) printf("-1\n");
    else printf("\n");
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;
    while (kase--) {
        init();
        scanf("%d%lf", &n, &D);
        S = 0;
        // ice
        for (int i = 1; i <= n; i++) {
            int x, y, _n, _m;
            scanf("%d%d%d%d", &x, &y, &_n, &_m);
            ice[i] = {x, y};
            add(i, n+i, _m);
            add(S, i, _n);
            tot += _n;
        }
        // link node
        for (int i = 1; i <= n; i++) for (int j = i+1; j <= n; j++) {
            if (check(ice[i], ice[j])) {
                add(n+i, j, inf);
                add(n+j, i, inf);
            }
        }

        // then solve
        solve();
    }
}