网络流24题

本文最后更新于：星期四, 二月 3日 2022, 9:15 晚上

写在前面

之前写的网络流24题，后来因为比赛耽搁了，想了想还是搬到博客上好了

餐巾计划问题

传送门

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

using namespace std;

#define ll long long
#define MAXN 10010
#define MAXM 1000010
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

struct Edge {
    int to, nxt;
    ll cap, flow, cost;
} edge[MAXM];

int head[MAXN], tot;
int pre[MAXN];
ll dis[MAXN];
bool vis[MAXN];
int N;

void Init(int n) {
    N = n;
    tot = 0;
    memset(head, -1, sizeof head);
}

void addedge(int u, int v, ll cap, ll cost) {
    edge[tot].to = v;
    edge[tot].cap = cap;
    edge[tot].cost = cost;
    edge[tot].flow = 0;
    edge[tot].nxt = head[u];
    head[u] = tot++;

    edge[tot].to = u;
    edge[tot].cap = 0;
    edge[tot].cost = -cost;
    edge[tot].flow = 0;
    edge[tot].nxt = head[v];
    head[v] = tot++;
}

bool SPFA(int s, int t) {
    queue<int> q;
    for (int i = 0; i < N; ++i) {
        dis[i] = INFLL;
        vis[i] = false;
        pre[i] = -1;
    }
    dis[s] = 0;
    vis[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return pre[t] != -1;
}

int minCostMaxflow(int s, int t, ll &cost) {
    int flow = 0;
    cost = 0;
    while (SPFA(s, t)) {
        ll Min = INFLL;
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
            Min = min(Min, 1ll * edge[i].cap - edge[i].flow);
        }
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
            edge[i].flow += Min;
            edge[i ^ 1].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
    return flow;
}

int n, a, b, c, d, e;

int main() {
    scanf("%d", &n);
    int S = 0, T = 2 * n + 1;
    Init(T + 1);
    for (int i = 1, x; i <= n; ++i) {
        scanf("%d", &x);
        addedge(S, i, x, 0);
        addedge(i + n, T, x, 0);
    }
    scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
    for (int i = 1; i <= n; ++i) {
        if (i + 1 <= n) {
            addedge(i, i + 1, INF, 0);
        }
        if (i + b <= n) {
            addedge(i, i + n + b, INF, c);
        }
        if (i + d <= n) {
            addedge(i, i + n + d, INF, e);
        }
        addedge(S, i + n, INF, a);
    }
    ll cost = 0;
    int flow = minCostMaxflow(S, T, cost);
    printf("%lld\n", cost);
    return 0;
}

飞行员配对方案问题

传送门

最大流裸题

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

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;

struct Edge {
    int to, flow, nxt;

    Edge() {}

    Edge(int to, int nxt, int flow) : to(to), nxt(nxt), flow(flow) {}
} edge[maxn << 1];

int head[maxn], dep[maxn];
int S, T;
int N, n, m, tot;

void Init(int n) {
    N = n;
    memset(head, -1, sizeof head);
    tot = 0;
}

void addedge(int u, int v, int w, int rw = 0) {
    edge[tot] = Edge(v, head[u], w);
    head[u] = tot++;
    edge[tot] = Edge(u, head[v], rw);
    head[v] = tot++;
}

bool BFS() {
    for (int i = 0; i < N; ++i) {
        dep[i] = -1;
    }
    queue<int> q;
    q.push(S);
    dep[S] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].flow && dep[edge[i].to] == -1) {
                dep[edge[i].to] = dep[u] + 1;
                q.push(edge[i].to);
            }
        }
    }
    return dep[T] != -1;
}

int DFS(int u, int f) {
    if (u == T || f == 0) return f;
    int w, used = 0;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
            w = DFS(edge[i].to, min(f - used, edge[i].flow));
            edge[i].flow -= w;
            edge[i ^ 1].flow += w;
            used += w;
            if (used == f) return f;
        }
    }
    if (!used) dep[u] = -1;
    return used;
}

int Dicnic() {
    int ans = 0;
    while (BFS()) {
        ans += DFS(S, INF);
    }
    return ans;
}

int main() {
    scanf("%d %d", &m, &n);
    S = 0, T = n + 1;
    Init(T + 1);
    int u, v;
    for (int i = 1; i <= m; ++i) {
        addedge(S, i, 1);
    }
    for (int i = m + 1; i <= n; ++i) {
        addedge(i, T, 1);
    }
    while (~scanf("%d %d", &u, &v)) {
        if (u == -1 && v == -1) break;
        addedge(u, v, 1);
    }
    int res = Dicnic();
    printf("%d\n", res);
    for (int i = 0; i < tot; i += 2) {
        if (edge[i].to == S || edge[i ^ 1].to == S) continue;
        if (edge[i].to == T || edge[i ^ 1].to == T) continue;
        if (edge[i].flow == 0) {
            printf("%d %d\n", edge[i].to, edge[i ^ 1].to);
        }
    }
    return 0;
}

软件补丁问题

传送门

最短路

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

using namespace std;

const int maxn = 1 << 21;

int n, m;
int b1[maxn], b2[maxn], f1[maxn], f2[maxn];
int cost[maxn];
int dis[maxn], vis[maxn];
char str[maxn];
int T;

bool judge(int S, int id) {
    if ((b1[id] | S) != S) {
        return false;
    }
    return (b2[id] & S) == 0;
}

void SPFA() {
    memset(dis, 0x3f, sizeof dis);
    queue<int> q;
    dis[T] = 0;
    vis[T] = true;
    q.push(T);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = 1; i <= m; ++i) {
            if (!judge(u, i)) {
                continue;
            }
            int now = u ^(u & f1[i]);
            now |= f2[i];
            if (dis[now] > dis[u] + cost[i]) {
                dis[now] = dis[u] + cost[i];
                if (!vis[now]) {
                    vis[now] = true;
                    q.push(now);
                }
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    T = 1 << n;
    T--;
    for (int i = 1; i <= m; ++i) {
        scanf("%d", cost + i);
        scanf("%s", str);
        for (int j = 0; j < n; ++j) {
            if (str[j] == '+') {
                b1[i] |= (1 << j);
            } else if (str[j] == '-') {
                b2[i] |= (1 << j);
            }
        }
        scanf("%s", str);
        for (int j = 0; j < n; ++j) {
            if (str[j] == '-') {
                f1[i] |= (1 << j);
            } else if (str[j] == '+') {
                f2[i] |= (1 << j);
            }
        }
    }
    SPFA();
    if (dis[0] == 0x3f3f3f3f) {
        dis[0] = 0;
    }
    printf("%d\n", dis[0]);
    return 0;
}

太空飞行计划问题

传送门

源点和实验室连边，流量为实验结果支付金额，实验室和实验仪器连边，流量为INF，实验器材与汇点连边，流量为器材成本，跑最大流。

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

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;

struct Edge {
    int to, flow, nxt;

    Edge() {}

    Edge(int to, int nxt, int flow) : to(to), nxt(nxt), flow(flow) {}
} edge[maxn << 1];

int head[maxn], dep[maxn];
int S, T;
int N, n, m, tot;

void Init(int n) {
    N = n;
    memset(head, -1, sizeof head);
    tot = 0;
}

void addedge(int u, int v, int w, int rw = 0) {
    edge[tot] = Edge(v, head[u], w);
    head[u] = tot++;
    edge[tot] = Edge(u, head[v], rw);
    head[v] = tot++;
}

bool BFS() {
    for (int i = 0; i < N; ++i) {
        dep[i] = -1;
    }
    queue<int> q;
    q.push(S);
    dep[S] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].flow && dep[edge[i].to] == -1) {
                dep[edge[i].to] = dep[u] + 1;
                q.push(edge[i].to);
            }
        }
    }
    return dep[T] != -1;
}

int DFS(int u, int f) {
    if (u == T || f == 0) return f;
    int w, used = 0;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
            w = DFS(edge[i].to, min(f - used, edge[i].flow));
            edge[i].flow -= w;
            edge[i ^ 1].flow += w;
            used += w;
            if (used == f) return f;
        }
    }
    if (!used) dep[u] = -1;
    return used;
}

int Dicnic() {
    int ans = 0;
    while (BFS()) {
        ans += DFS(S, INF);
    }
    return ans;
}

char buf[' '];

int main() {
    scanf("%d %d", &n, &m);
    S = 0, T = n + m + 1;
    Init(T + 1);
    int sum = 0;
    for (int i = 1, x; i <= n; ++i) {
        scanf("%d", &x);
        addedge(S, i, x);
        sum += x;
        std::cin.getline(buf, ' ');
        for (int j = 0; ~sscanf(buf + j, "%d", &x); ++j) {
            j += !x;
            addedge(i, n + x, INF);
            for (j += !x; x; x /= 10) ++j;
        }
    }
    for (int i = 1, x; i <= m; ++i) {
        scanf("%d", &x);
        addedge(n + i, T, x);
    }
    sum -= Dicnic();
    int tmp = 0;
    for (int i = n; !tmp; --i) tmp = i * (dep[i] != -1);
    for (int i = 1; i <= tmp; ++i) {
        if (dep[i] != -1) {
            printf("%d%c", i, " \n"[i == tmp]);
        }
    }
    tmp = 0;
    for (int i = m; !tmp; --i) tmp = i * (dep[i + n] != -1);
    for (int i = 1; i <= tmp; ++i) {
        if (dep[i + n] != -1) {
            printf("%d%c", i, " \n"[i == tmp]);
        }
    }
    printf("%d\n", sum);
    return 0;
}

试题库问题

传送门

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

using namespace std;

#define MAXN 10010
#define MAXM 100010
#define INF 0x3f3f3f3f

struct Edge {
    int to, flow, nxt;

    Edge() {}

    Edge(int to, int nxt, int flow) : to(to), nxt(nxt), flow(flow) {}
} edge[MAXM];

int head[MAXN], dep[MAXN];
int S, T;
int N, tot;

void Init(int n) {
    N = n;
    tot = 0;
    memset(head, -1, sizeof head);
}

void addedge(int u, int v, int w, int rw = 0) {
    edge[tot] = Edge(v, head[u], w);
    head[u] = tot++;
    edge[tot] = Edge(u, head[v], rw);
    head[v] = tot++;
}

bool BFS() {
    for (int i = 0; i < N; ++i) {
        dep[i] = -1;
    }
    dep[S] = 1;
    queue<int> q;
    q.push(S);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].flow && dep[edge[i].to] == -1) {
                dep[edge[i].to] = dep[u] + 1;
                q.push(edge[i].to);
            }
        }
    }
    return dep[T] != -1;
}

int DFS(int u, int f) {
    if (u == T || f == 0) return f;
    int w, used = 0;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
            w = DFS(edge[i].to, min(f - used, edge[i].flow));
            edge[i].flow -= w;
            edge[i ^ 1].flow += w;
            used += w;
            if (used == f) return f;
        }
    }
    if (!used) dep[u] = -1;
    return used;
}

int Dinnic() {
    int ans = 0;
    while (BFS()) {
        ans += DFS(S, INF);
    }
    return ans;
}

int k, n;
vector<vector<int> > G;

int main() {
    scanf("%d %d", &k, &n);
    G.resize(k + 1);
    S = 0, T = k + n + 1;
    Init(T + 1);
    int sum = 0;
    for (int i = 1, x; i <= k; ++i) {
        scanf("%d", &x);
        addedge(i + n, T, x);
        sum += x;
    }
    for (int i = 1, p, x; i <= n; ++i) {
        scanf("%d", &p);
        addedge(S, i, 1);
        for (int j = 1; j <= p; ++j) {
            scanf("%d", &x);
            addedge(i, x + n, 1);
        }
    }
    int ans = Dinnic();
    if (ans != sum) {
        puts("No Solution!");
        return 0;
    }
    for (int u = 1; u <= n; ++u) {
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].to > n && edge[i].flow == 0) {
                G[edge[i].to - n].push_back(u);
            }
        }
    }
    for (int i = 1; i <= k; ++i) {
        printf("%d:", i);
        for (auto it : G[i]) {
            printf(" %d", it);
        }
        puts("");
    }
    return 0;
}

最小路径覆盖问题

传送门

最小路径覆盖问题裸题

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

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;

struct Edge {
    int to, flow, nxt;

    Edge() {}

    Edge(int to, int nxt, int flow) : to(to), nxt(nxt), flow(flow) {}
} edge[maxn << 1];

int head[maxn], dep[maxn];
int S, T;
int N, n, m, tot;

void Init(int n) {
    N = n;
    memset(head, -1, sizeof head);
    tot = 0;
}

void addedge(int u, int v, int w, int rw = 0) {
    edge[tot] = Edge(v, head[u], w);
    head[u] = tot++;
    edge[tot] = Edge(u, head[v], rw);
    head[v] = tot++;
}

bool BFS() {
    for (int i = 0; i < N; ++i) {
        dep[i] = -1;
    }
    queue<int> q;
    q.push(S);
    dep[S] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].flow && dep[edge[i].to] == -1) {
                dep[edge[i].to] = dep[u] + 1;
                q.push(edge[i].to);
            }
        }
    }
    return dep[T] != -1;
}

int DFS(int u, int f) {
    if (u == T || f == 0) return f;
    int w, used = 0;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
            w = DFS(edge[i].to, min(f - used, edge[i].flow));
            edge[i].flow -= w;
            edge[i ^ 1].flow += w;
            used += w;
            if (used == f) return f;
        }
    }
    if (!used) dep[u] = -1;
    return used;
}

int Dicnic() {
    int ans = 0;
    while (BFS()) {
        ans += DFS(S, INF);
    }
    return ans;
}

int fa[maxn];

int find(int x) { return x == fa[x] ? fa[x] : fa[x] = find(fa[x]); }

void Unin(int x, int y) {
    x = find(x), y = find(y);
    fa[x] = y;
}

void output(int x) {
    printf("%d ", x);
    for (int i = head[x]; ~i; i = edge[i].nxt) {
        if (edge[i].flow == 0 && edge[i].to > n) {
            output(edge[i].to - n);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    S = 0, T = 2 * n + 1;
    Init(T + 1);
    for (int i = 1, u, v; i <= m; ++i) {
        scanf("%d %d", &u, &v);
        addedge(u, v + n, 1);
    }
    for (int i = 1; i <= n; ++i) {
        addedge(S, i, 1);
        addedge(i + n, T, 1);
    }
    Dicnic();
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
    for (int u = 1; u <= n; ++u) {
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].to == S || edge[i].to == T) continue;
            if (edge[i].flow == 0) {
                Unin(edge[i].to - n, u);
            }
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (find(i) == i) {
            output(i);
            putchar('\n');
            cnt++;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

最长不下降子序列问题

传送门

第一个问题用dp求解

第二个问题

dp[i]==1dp[i]==1

源点和i的入点连边

dp[i]==lendp[i] == len

ii的出点和汇点连边

然后a[i]>=a[j]a[i]>=a[j]且dp[i]=dp[j]+1dp[i]=dp[j]+1则两个点连边

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

using namespace std;

#define MAXN 10010
#define MAXM 2000010
#define INF 0x3f3f3f3f

struct Edge {
    int to, flow, nxt;

    Edge() {}

    Edge(int to, int nxt, int flow) : to(to), nxt(nxt), flow(flow) {}
} edge[MAXM];

int head[MAXN], dep[MAXN];
int S, T;
int N, tot;

void Init(int n) {
    N = n;
    tot = 0;
    memset(head, -1, sizeof head);
}

void addedge(int u, int v, int w, int rw = 0) {
    edge[tot] = Edge(v, head[u], w);
    head[u] = tot++;
    edge[tot] = Edge(u, head[v], rw);
    head[v] = tot++;
}

bool BFS() {
    for (int i = 0; i < N; ++i) {
        dep[i] = -1;
    }
    dep[S] = 1;
    queue<int> q;
    q.push(S);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].flow && dep[edge[i].to] == -1) {
                dep[edge[i].to] = dep[u] + 1;
                q.push(edge[i].to);
            }
        }
    }
    return dep[T] != -1;
}

int DFS(int u, int f) {
    if (u == T || f == 0) return f;
    int w, used = 0;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
            w = DFS(edge[i].to, min(f - used, edge[i].flow));
            edge[i].flow -= w;
            edge[i ^ 1].flow += w;
            used += w;
            if (used == f) return f;
        }
    }
    if (!used) dep[u] = -1;
    return used;
}

int Dicnic() {
    int ans = 0;
    while (BFS()) {
        ans += DFS(S, INF);
    }
    return ans;
}

int n;
int arr[550];
int dp[550];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", arr + i);
    }
    int len = 0;
    for (int i = 1; i <= n; ++i) {
        dp[i] = 1;
        for (int j = 1; j < i; ++j) {
            if (arr[j] <= arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        len = max(len, dp[i]);
    }
    printf("%d\n", len);
    S = 0, T = n * 2 + 1;
    Init(T + 1);
    for (int i = 1; i <= n; ++i) {
        if (dp[i] == 1) {
            addedge(S, i, 1);
        }
        if (dp[i] == len) {
            addedge(i + n, T, 1);
        }
        addedge(i, i + n, 1);
        for (int j = 1; j < i; ++j) {
            if (arr[j] <= arr[i] && dp[i] == dp[j] + 1) {
                addedge(j + n, i, 1);
            }
        }
    }
    int ans = Dicnic();
    printf("%d\n", ans);
    addedge(S, 1, INF);
    addedge(1, 1 + n, INF);
    if (dp[n] == len) {
        addedge(n, n * 2, INF);
        addedge(n * 2, T, INF);
    }
    ans += Dicnic();
    printf("%d\n", ans);
    return 0;
}

方格取数问题

传送门

将图用黑白色染色，其中(i+j)(mod2)=1(i+j) \pmod {2} = 1的为黑色

源点和黑色相连，白色与汇点相连

黑色白色有关的额相连

跑最小割，答案为sum−sum-最小割

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

using namespace std;

#define ll long long
#define MAXN 100010
#define MAXM 2000010
#define INF 0x3f3f3f3f

struct Edge {
    int to, flow, nxt;

    Edge() {}

    Edge(int to, int nxt, int flow) : to(to), nxt(nxt), flow(flow) {}
} edge[MAXM];

int head[MAXN], dep[MAXN];
int S, T;
int N, tot;

void Init(int n) {
    N = n;
    tot = 0;
    memset(head, -1, sizeof head);
}

void addedge(int u, int v, int w, int rw = 0) {
    edge[tot] = Edge(v, head[u], w);
    head[u] = tot++;
    edge[tot] = Edge(u, head[v], rw);
    head[v] = tot++;
}

bool BFS() {
    for (int i = 0; i < N; ++i) {
        dep[i] = -1;
    }
    dep[S] = 1;
    queue<int> q;
    q.push(S);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].flow && dep[edge[i].to] == -1) {
                dep[edge[i].to] = dep[u] + 1;
                q.push(edge[i].to);
            }
        }
    }
    return dep[T] != -1;
}

int DFS(int u, int f) {
    if (u == T || f == 0) return f;
    int w, used = 0;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
            w = DFS(edge[i].to, min(f - used, edge[i].flow));
            edge[i].flow -= w;
            edge[i ^ 1].flow += w;
            used += w;
            if (used == f) return f;
        }
    }
    if (!used) dep[u] = -1;
    return used;
}

ll Dicnic() {
    ll ans = 0;
    while (BFS()) {
        ans += DFS(S, INF);
    }
    return ans;
}


int n, m;
ll arr[110][110];
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

int get(int x, int y) {
    return (x - 1) * m + y;
}

int main() {
    scanf("%d %d", &n, &m);
    S = 0, T = n * m + 1;
    Init(T + 1);
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%lld", &arr[i][j]);
            ans += arr[i][j];
            if ((i + j) % 2) {
                addedge(S, get(i, j), arr[i][j]);
            } else {
                addedge(get(i, j), T, arr[i][j]);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if ((i + j) % 2) {
                for (int k = 0; k < 4; ++k) {
                    int x = i + dir[k][0];
                    int y = j + dir[k][1];
                    if (x < 1 || x > n || y < 1 || y > m) continue;
                    addedge(get(i, j), get(x, y), INF);
                }
            }
        }
    }
    ans -= Dicnic();
    printf("%lld\n", ans);
    return 0;
}

圆桌问题

传送门

源点与单位连边，流量为代表数

餐桌和汇点连边，流量为餐桌容量

每个单位都和每个餐桌连边，跑最大流

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

using namespace std;

#define ll long long
#define MAXN 100010
#define MAXM 2000010
#define INF 0x3f3f3f3f

struct Edge {
    int to, flow, nxt;

    Edge() {}

    Edge(int to, int nxt, int flow) : to(to), nxt(nxt), flow(flow) {}
} edge[MAXM];

int head[MAXN], dep[MAXN];
int S, T;
int N, tot;

void Init(int n) {
    N = n;
    tot = 0;
    memset(head, -1, sizeof head);
}

void addedge(int u, int v, int w, int rw = 0) {
    edge[tot] = Edge(v, head[u], w);
    head[u] = tot++;
    edge[tot] = Edge(u, head[v], rw);
    head[v] = tot++;
}

bool BFS() {
    for (int i = 0; i < N; ++i) {
        dep[i] = -1;
    }
    dep[S] = 1;
    queue<int> q;
    q.push(S);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].flow && dep[edge[i].to] == -1) {
                dep[edge[i].to] = dep[u] + 1;
                q.push(edge[i].to);
            }
        }
    }
    return dep[T] != -1;
}

int DFS(int u, int f) {
    if (u == T || f == 0) return f;
    int w, used = 0;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
            w = DFS(edge[i].to, min(f - used, edge[i].flow));
            edge[i].flow -= w;
            edge[i ^ 1].flow += w;
            used += w;
            if (used == f) return f;
        }
    }
    if (!used) dep[u] = -1;
    return used;
}

int Dicnic() {
    ll ans = 0;
    while (BFS()) {
        ans += DFS(S, INF);
    }
    return ans;
}

int n, m;
int arr[310], brr[310];
vector<int> G[310];

int main() {
    scanf("%d %d", &n, &m);
    S = 0, T = n + m + 1;
    Init(T + 1);
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", arr + i);
        sum += arr[i];
        addedge(S, i, arr[i]);
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d", brr + i);
        addedge(i + n, T, brr[i]);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            addedge(i, j + n, 1);
        }
    }
    int ans = Dicnic();
    if (ans == sum) {
        puts("1");
        for (int u = 1; u <= n; ++u) {
            for (int i = head[u]; ~i; i = edge[i].nxt) {
                if (edge[i].to > n && edge[i].flow == 0) {
                    G[u].push_back(edge[i].to - n);
                }
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 0, len = G[i].size(); j < len; ++j) {
                printf("%d%c", G[i][j], " \n"[j == len - 1]);
            }
        }
    } else {
        puts("0");
    }
    return 0;
}

骑士共存问题

传送门

将图染色 染成黑白色

黑色与源点相连， 白色与汇点相连，相关联的黑白点相连。

跑最小割，答案为n⋅n−m−n\cdot 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
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define MAXN 100010
#define MAXM 2000010
#define INF 0x3f3f3f3f

struct Edge {
    int to, flow, nxt;

    Edge() {}

    Edge(int to, int nxt, int flow) : to(to), nxt(nxt), flow(flow) {}
} edge[MAXM];

int head[MAXN], dep[MAXN];
int S, T;
int N, tot;

void Init(int n) {
    N = n;
    tot = 0;
    memset(head, -1, sizeof head);
}

void addedge(int u, int v, int w, int rw = 0) {
    edge[tot] = Edge(v, head[u], w);
    head[u] = tot++;
    edge[tot] = Edge(u, head[v], rw);
    head[v] = tot++;
}

bool BFS() {
    for (int i = 0; i < N; ++i) {
        dep[i] = -1;
    }
    dep[S] = 1;
    queue<int> q;
    q.push(S);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            if (edge[i].flow && dep[edge[i].to] == -1) {
                dep[edge[i].to] = dep[u] + 1;
                q.push(edge[i].to);
            }
        }
    }
    return dep[T] != -1;
}

int DFS(int u, int f) {
    if (u == T || f == 0) return f;
    int w, used = 0;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
            w = DFS(edge[i].to, min(f - used, edge[i].flow));
            edge[i].flow -= w;
            edge[i ^ 1].flow += w;
            used += w;
            if (used == f) return f;
        }
    }
    if (!used) dep[u] = -1;
    return used;
}

int Dicnic() {
    ll ans = 0;
    while (BFS()) {
        ans += DFS(S, INF);
    }
    return ans;
}

int n, m;
int vis[210][210];
int dir[8][2] = {{-2, -1},
                 {-2, 1},
                 {-1, -2},
                 {-1, 2},
                 {1,  -2},
                 {1,  2},
                 {2,  -1},
                 {2,  1}};

int get(int x, int y) {
    return (x - 1) * n + y;
}

int main() {
    scanf("%d %d", &n, &m);
    S = 0, T = n * n + 1;
    Init(T + 1);
    for (int i = 1, x, y; i <= m; ++i) {
        scanf("%d %d", &x, &y);
        vis[x][y] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (vis[i][j]) continue;
            if ((i + j) % 2) {
                addedge(S, get(i, j), 1);
            } else {
                addedge(get(i, j), T, 1);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (vis[i][j]) continue;
            if ((i + j) % 2) {
                for (int k = 0; k < 8; ++k) {
                    int x = i + dir[k][0];
                    int y = j + dir[k][1];
                    if (x < 1 || x > n || y < 1 || y > n || vis[x][y]) continue;
                    addedge(get(i, j), get(x, y), INF);
                }
            }
        }
    }
    int ans = Dicnic();
    printf("%d\n", n * n - m - ans);
    return 0;
}

分配问题

传送门

费用流分别跑最大最小值

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

using namespace std;

#define MAXN 10010
#define MAXM 100010
#define INF 0x3f3f3f3f

struct Edge {
    int to, nxt, cap, flow, cost;

    Edge() {}

    Edge(int to, int nxt, int cap, int flow, int cost) : to(to), nxt(nxt), cap(cap), flow(flow), cost(cost) {}
} edge[MAXM];

int head[MAXN], tot;
int pre[MAXN], dis[MAXN];
bool vis[MAXN];
int N;

void Init(int n) {
    N = n;
    tot = 0;
    memset(head, -1, sizeof(head));
}

void addedge(int u, int v, int cap, int cost) {
    edge[tot] = Edge(v, head[u], cap, 0, cost);
    head[u] = tot++;
    edge[tot] = Edge(u, head[v], 0, 0, -cost);
    head[v] = tot++;
}

bool SPFA(int s, int t) {
    queue<int> q;
    for (int i = 0; i < N; ++i) {
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    vis[s] = true;
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return pre[t] != -1;
}

int minCostMaxflow(int s, int t, int &cost) {
    int flow = 0;
    cost = 0;
    while (SPFA(s, t)) {
        int Min = INF;
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
            Min = min(Min, edge[i].cap - edge[i].flow);
        }
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
            edge[i].flow += Min;
            edge[i ^ 1].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
    return flow;
}

int n;
int arr[110][110];

int main() {
    scanf("%d", &n);
    int S = 0, T = 2 * n + 1;
    Init(T + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &arr[i][j]);
            addedge(i, j + n, 1, arr[i][j]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        addedge(S, i, 1, 0);
        addedge(i + n, T, 1, 0);
    }
    int cost = 0;
    int flow = minCostMaxflow(S, T, cost);
    printf("%d\n", cost);
    Init(T + 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            addedge(i, j + n, 1, -arr[i][j]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        addedge(S, i, 1, 0);
        addedge(i + n, T, 1, 0);
    }
    cost = 0;
    flow = minCostMaxflow(S, T, cost);
    printf("%d\n", -cost);
    return 0;
}

运输问题

传送门

最小费用最大流

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

using namespace std;

#define MAXN 10010
#define MAXM 100010
#define INF 0x3f3f3f3f

struct Edge {
    int to, nxt, cap, flow, cost;

    Edge() {}

    Edge(int to, int nxt, int cap, int flow, int cost) : to(to), nxt(nxt), cap(cap), flow(flow), cost(cost) {}
} edge[MAXM];

int head[MAXN], tot;
int pre[MAXN], dis[MAXN];
bool vis[MAXN];
int N;

void Init(int n) {
    N = n;
    tot = 0;
    memset(head, -1, sizeof(head));
}

void addedge(int u, int v, int cap, int cost) {
    edge[tot] = Edge(v, head[u], cap, 0, cost);
    head[u] = tot++;
    edge[tot] = Edge(u, head[v], 0, 0, -cost);
    head[v] = tot++;
}

bool SPFA(int s, int t) {
    queue<int> q;
    for (int i = 0; i < N; ++i) {
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    vis[s] = true;
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return pre[t] != -1;
}

int minCostMaxflow(int s, int t, int &cost) {
    int flow = 0;
    cost = 0;
    while (SPFA(s, t)) {
        int Min = INF;
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
            Min = min(Min, edge[i].cap - edge[i].flow);
        }
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
            edge[i].flow += Min;
            edge[i ^ 1].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
    return flow;
}

int n, m;
int arr[110], brr[110], crr[110][110];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", arr + i);
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d", brr + i);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d", &crr[i][j]);
        }
    }
    int S = 0, T = n + m + 1;
    int cost, flow;
    Init(T + 1);
    for (int i = 1; i <= n; ++i) {
        addedge(S, i, arr[i], 0);
    }
    for (int i = 1; i <= m; ++i) {
        addedge(i + n, T, brr[i], 0);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            addedge(i, j + n, INF, crr[i][j]);
        }
    }
    flow = minCostMaxflow(S, T, cost);
    printf("%d\n", cost);
    Init(T + 1);
    for (int i = 1; i <= n; ++i) {
        addedge(S, i, arr[i], 0);
    }
    for (int i = 1; i <= m; ++i) {
        addedge(i + n, T, brr[i], 0);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            addedge(i, j + n, INF, -crr[i][j]);
        }
    }
    flow = minCostMaxflow(S, T, cost);
    printf("%d\n", -cost);
    return 0;
}

负载平衡问题

传送门

费用流

如果需要移出的和源点相连，流量为移出的量，费用为0

如果需要移入的和汇点相连，流量为移入的量，费用为0

每个点和相邻的连边，流量为INF， 费用为1

跑费用流

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

using namespace std;

#define MAXN 10010
#define MAXM 100010
#define INF 0x3f3f3f3f

struct Edge {
    int to, nxt, cap, flow, cost;

    Edge() {}

    Edge(int to, int nxt, int cap, int flow, int cost) : to(to), nxt(nxt), cap(cap), flow(flow), cost(cost) {}
} edge[MAXM];

int head[MAXN], tot;
int pre[MAXN], dis[MAXN];
bool vis[MAXN];
int N;

void Init(int n) {
    N = n;
    tot = 0;
    memset(head, -1, sizeof(head));
}

void addedge(int u, int v, int cap, int cost) {
    edge[tot] = Edge(v, head[u], cap, 0, cost);
    head[u] = tot++;
    edge[tot] = Edge(u, head[v], 0, 0, -cost);
    head[v] = tot++;
}

bool SPFA(int s, int t) {
    queue<int> q;
    for (int i = 0; i < N; ++i) {
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    vis[s] = true;
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost) {
                dis[v] = dis[u] + edge[i].cost;
                pre[v] = i;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return pre[t] != -1;
}

int minCostMaxflow(int s, int t, int &cost) {
    int flow = 0;
    cost = 0;
    while (SPFA(s, t)) {
        int Min = INF;
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
            Min = min(Min, edge[i].cap - edge[i].flow);
        }
        for (int i = pre[t]; ~i; i = pre[edge[i ^ 1].to]) {
            edge[i].flow += Min;
            edge[i ^ 1].flow -= Min;
            cost += edge[i].cost * Min;
        }
        flow += Min;
    }
    return flow;
}

int n;
int arr[110];

int main() {
    scanf("%d", &n);
    int S = 0, T = n + 1;
    Init(T + 1);
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", arr + i);
        sum += arr[i];
    }
    sum /= n;
    for (int i = 1; i <= n; ++i) {
        if (arr[i] > sum) {
            addedge(S, i, arr[i] - sum, 0);
        } else {
            addedge(i, T, sum - arr[i], 0);
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (i == 1) {
            addedge(1, 2, INF, 1);
            addedge(1, n, INF, 1);
        } else if (i == n) {
            addedge(n, n - 1, INF, 1);
            addedge(n, 1, INF, 1);
        } else {
            addedge(i, i + 1, INF, 1);
            addedge(i, i - 1, INF, 1);
        }
    }
    int cost = 0;
    int flow = minCostMaxflow(S, T, cost);
    printf("%d\n", cost);
    return 0;
}
知识点

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！