关键边

Acwing2236
Acwing2236

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
const int maxn = 510, maxm = (maxn + 5000) * 2;
const int inf = 0x3f3f3f3f;
int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
int n, m, 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 d[maxn], cur[maxn];
bool bfs() {
    memset(d, -1, sizeof d);
    queue<int> q;
    d[S] = 0, cur[S] = head[S];
    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;
}

bool vis_s[maxn], vis_t[maxn];
void dfs(int u, bool st[], int fl) {
    st[u] = true;
    for (int i = head[u]; i; i = ne[i]) {
        int j = i ^ fl, v = ver[i];
        if (!st[v] && e[j]) dfs(v, st, fl);
    }
}

void solve() {
    int res = 0;
    for (int i = 2; i < 2 + m*2; i += 2) {
        if (!e[i] && vis_s[ ver[i^1] ] && vis_t[ ver[i] ]) res++;
    }
    printf("%d\n", res);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    S = 0, T = n-1;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    dinic();
    dfs(S, vis_s, 0);
    dfs(T, vis_t, 1);

    solve();
}

二分与最大流

Acwing2277
Acwing2277

特殊情况
如果是无向图，要求每条边最多只能走一次，在建流网络的时候
(u,v)(u, v) 正向走一次，(v,u)(v, u) 反向又走了一次，等价于没有流
把相应的边删去即可

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
const int maxn = 200 + 10, maxm = (maxn + 40000) * 2;
const int inf = 0x3f3f3f3f;
int head[maxn], ver[maxm], e[maxm], w[maxm], ne[maxm], idx = 1;
int n, m, S, T, K;

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

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;
}

bool check(int x) {
    for (int i = 2; i <= idx; i++) {
        if (w[i] > x) e[i] = 0;
        else e[i] = 1;
    }
    return dinic() >= K;
}

void solve() {
    int l = 1, r = 1e6;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d", &n, &m, &K);
    S = 1, T = n;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    // then solve
    solve();
}

分层图和最大流判定

dinicgraph
Acwing2187
Acwing2187-01
Acwing2187-02

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

int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
int n, m, K, 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 pa[maxn];
int found(int x) {
    return x == pa[x] ? x : pa[x] = found(pa[x]);
}

class Ship {
public:
    int H, r, s[16];
} ships[30];

inline int get(int day, int i) {
    return day * (n+2) + 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;
}

void solve() {
    add(S, get(0, 0), K);
    add(get(0, n+1), T, inf);

    int day = 1, res = 0;
    while (true) {
        add(get(day, n+1), T, inf);
        for (int i = 0; i <= n+1; i++) {
            add(get(day-1, i), get(day, i), inf);
        }

        for (int i = 0; i < m; i++) {
            int r = ships[i].r;
            int s1 = ships[i].s[ (day-1) % r ], s2 = ships[i].s[ day % r ];
            add(get(day-1, s1), get(day, s2), ships[i].H);
        }

        res += dinic();
        if (res >= K) break;
        day++;
    }
    printf("%d\n", day);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 0; i <= 30; i++) pa[i] = i;
    S = maxn - 2, T = maxn - 1;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &ships[i].H, &ships[i].r);
        int b = ships[i].r;
        for (int j = 0; j < b; j++) {
            scanf("%d", &ships[i].s[j]);
            if (ships[i].s[j] == -1) ships[i].s[j] = n+1;
            if (j) pa[found(ships[i].s[j-1])] = found(ships[i].s[j]);
        }
    }

    if (found(0) != found(n+1)) {
        puts("0");
        return 0;
    }

    // then solve
    solve();
}

分层图最大流方案输出

codeforces101388B

  • 第 ii 个星球，第 dayday 天的状态节点是 get(day,i)\textbf{get}(day, i)
  • 为了便于输出，mm 条双向隧道可以用二元组 edges(u,v)\text{edges}(u, v) 预先存起来

    c(get(day−1,u), get(day,v))=1c(get(day−1,v), get(day,u))=1\begin{gathered} c\left( \text{get}(day-1, u), \ \text{get}(day, v) \right) = 1 \\ c\left( \text{get}(day-1, v), \ \text{get}(day, u) \right) = 1 \end{gathered}

    用一个 map: PII→int\textbf{map:} \ \text{PII} \to \text{int} 分别记录这两条边的编号，当然，只需要记录正向边

    map{(day−1,u),(day,v)}=idx1map{(day−1,v),(day,u)}=idx2\begin{gathered} \text{map}\{ (day-1, u), (day, v) \} = \text{idx}_1 \\ \text{map}\{ (day-1, v), (day, u) \} = \text{idx}_2 \end{gathered}

这里我们用 EE 表示流网络中的容量边，用 ee 表示隧道边

  • 输出的时候从第 00 天到第 dayday 天依次输出，需要记录一下 i∈[1⋯K]i \in [1\cdots K] 每个飞行器位置 location[i]\text{location}[i]
    初始化 location[1⋯K]=s\text{location}[1\cdots K] = s（在起点处），假设当前是第 pp 天：
    • for ∀p∈[0⋯day]\textbf{for} \ \forall p \in [0\cdots day]，对于第 pp 天，初始化这一天的决策集合 sol[⋯ ]\textbf{sol}[\cdots]：
      for ∀i∈[0,m)\textbf{for} \ \forall i \in [0, m) 依次检查每一条隧道，对于隧道 e(i):(u,v)\text{e}(i):(u, v)
      用 ∣f1∣|f1| 表示 (p−1,u)→(p,v)(p-1, u) \to (p, v) 的流量，用 ∣f2∣|f2| 表示 (p−1,v)→(p,u)(p-1, v) \to (p, u) 的流量

      ∣f1∣=E(map{(p−1,u),(p,v)}⊕1)∣f2∣=E(map{(p−1,v),(p,u)}⊕1)\begin{gathered} |f1| = E\left(\quad \text{map}\{ (p-1, u), (p, v) \} \oplus 1 \quad \right) \\ |f2| = E\left(\quad \text{map}\{ (p-1, v), (p, u) \} \oplus 1 \quad \right) \end{gathered}

      {∣f1∣=1 and ∣f2∣=0(u,v)加入决策集 sol∣f2∣=1 and ∣f1∣=0(v,u)加入决策集 sol\begin{cases} |f1| = 1 \ \textbf{and} \ |f2| = 0 && (u, v) \text{加入决策集 sol} \\ |f2| = 1 \ \textbf{and} \ |f1| = 0 && (v, u) \text{加入决策集 sol} \end{cases}

    • 初始化数组 moved[1⋯K]=0\text{moved}[1 \cdots K] = 0，表示这一天没有飞机起飞
      for ∀i∈sol[⋯ ]\textbf{for} \ \forall i \in \text{sol}[\cdots] ，遍历决策集，对于 sol[i]:(u,v)\textbf{sol}[i]: (u, v)，遍历每架飞机
      for ∀j∈[1⋯K]\quad \textbf{for} \ \forall j \in [1\cdots K]，if location[j]=u and moved(j)=0\textbf{if} \ \text{location}[j] = u \ \textbf{and} \ \text{moved}(j) = 0
      location[j]←v,moved[j]←1,print(j,v)\quad \quad \text{location}[j] \leftarrow v, \quad \text{moved}[j] \leftarrow 1, \quad \text{print}(j, v)
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
typedef pair<int, int> PII;
const int maxn = 50010, maxm = (maxn + 1000 + 200*1000)*2 + 10;
const int inf = 0x3f3f3f3f;
int n, m, K, s, t, S, T;
vector<PII> tunnel;
map<PII, int> mp;

int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
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;
}

inline int get(int day, int i) {
    return day*(n+1) + 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 day = 1;
void solve() {
    add(S, get(0, s), K);
    add(get(0, t), T, inf);
    day = 1;
    int res = 0;
    while (true) {
        add(get(day, t), T, inf);
        for (int i = 1; i <= n; i++) add(get(day-1, i), get(day, i), inf);
        for (auto x : tunnel) {
            int u = x.first, v = x.second;
            add(get(day-1, u), get(day, v), 1);
            mp[ {get(day-1, u), get(day, v)} ] = idx - 1;

            add(get(day-1, v), get(day, u), 1);
            mp[ {get(day-1, v), get(day, u)} ] = idx - 1;
        }

        res += dinic();
        if (res >= K) break;
        day++;
    }
    printf("%d\n", day);
}

void out() {
    vector<int> location(K, s);
    for (int p = 1; p <= day; p++) {
        vector<PII> sol;
        vector<int> moved(K, 0);

        for (auto x : tunnel) {
            int u = x.first, v = x.second;
            int id1 = mp[ {get(p-1, u), get(p, v)} ];
            int id2 = mp[ {get(p-1, v), get(p, u)} ];

            int f1 = e[id1 ^ 1], f2 = e[id2 ^ 1];
            if (f1 == 1 && f2 == 0) sol.push_back( {u, v} );
            if (f1 == 0 && f2 == 1) sol.push_back( {v, u} );
        }

        printf("%d", (int)sol.size());

        vector<PII> ans;
        for (auto x : sol) {
            int u = x.first, v = x.second;
            for (int i = 0; i < K; i++) {
                if (!moved[i] && location[i] == u) {
                    ans.push_back( {i+1, v} );
                    moved[i] = true;
                    location[i] = v;
                    break;
                }
            }
        }
        sort(ans.begin(), ans.end());
        for (auto x : ans) printf(" %d %d", x.first, x.second);
        printf("\n");
    }
}

int main() {
    freopen("bring.in", "r", stdin);
    freopen("bring.out", "w", stdout);
    scanf("%d%d%d%d%d", &n, &m, &K, &s, &t);
    S = maxn-1, T = maxn-2;
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        tunnel.push_back({u, v});
    }

    // solve
    solve();

    // out
    out();
}

匹配与拆点

Acwing2240
Acwing2240-01
Acwing2240-02

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
const int maxn = 400 + 10, maxm = (maxn + 410000) * 2;
const int inf = 0x3f3f3f3f;
int n, F, D, S, T;

int head[maxn], ver[maxm], e[maxm], ne[maxm], idx = 1;
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 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%d%d", &n, &F, &D);
    S = 0, T = 2*n + F + D + 2;

    // prework
    for (int i = 1; i <= F; i++) add(S, 2*n + i, 1);
    for (int i = 1; i <= D; i++) add(2*n + F + i, T, 1);
    for (int i = 1; i <= n; i++) add(i, n+i, 1);

    // get data
    for (int i = 1; i <= n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        while (a--) {
            int t;
            scanf("%d", &t);
            add(2*n + t, i, 1);
        }
        while (b--) {
            int t;
            scanf("%d", &t);
            add(n+i, 2*n + F + t, 1);
        }
    }

    int ans = dinic();
    printf("%d\n", ans);
}