「网络流 24 题」

题目名称 概述 题目名称 概述 题目名称 概述
搭配飞行员 二分图最大匹配 航空路线问题 费用流 运输问题 费用流
最小路径覆盖 最小路径覆盖 分配问题 二分图带权匹配 负载平衡 ..不解释..
魔术球 最小路径覆盖 星际转移 动态网络流? 最长 k 可重区间集 费用流碾压动态规划系列
太空飞行计划 最大权闭合子图 软件补丁 最短路? 孤岛营救问题 最短路?
圆桌聚餐 最大流满流 汽车加油行驶问题 最短路? 深海机器人问题 费用流
试题库 最大流满流 数字梯形 费用流限流问题 最长 k 可重线段集问题 费用流
骑士共存问题 转化为二分图解决 最长递增子序列 乱七八糟的限流 火星探险问题 费用流及其方案输出
餐巾计划 费用流 方格取数 最小割 完结撒花

搭配飞行员

题意

飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞行,问如何搭配驾驶员才能使出航的飞机最多。

因为驾驶工作分工严格,两个正驾驶员或两个副驾驶员都不能同机飞行。

题解

懒得打网络流了,直接匈牙利吧,又短又快

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
#include <bits/stdc++.h> 
typedef long long ll;
const int maxn = 200;
int mat[maxn], ans;
bool vis[maxn];
std::vector<int>G[maxn];
bool dfs(int u) {
if (vis[u]) return false; vis[u] = true;
for (int i = G[u].size() - 1; ~i; i--) {
int v = G[u][i];
if (!mat[v] || dfs(mat[v])) {
mat[v] = u; return true;
}
}
return false;
}
int main() {
int n, m; scanf("%d%d", &n, &m);
int x, y;
while (scanf("%d%d", &x, &y) != EOF)
G[x].push_back(y);
for (int i = 1; i <= m; i++) {
memset(vis, 0, sizeof(vis));
if (dfs(i)) ans++;
}
printf("%d", ans);
return 0;
}

最小路径覆盖

题意

给定有向图 $G=(V,E)$。设 $P$ 是 $G$ 的一个简单路(顶点不相交)的集合。如果 $V$ 中每个顶点恰好在 $P$ 的一条路上,则称 $P$ 是 $G$ 的一个路径覆盖。$P$ 中路径可以从 $V$ 的任何一个顶点开始,长度也是任意的,特别地,可以为 $0$。$G$ 的最小路径覆盖是 $G$ 的所含路径条数最少的路径覆盖。

设计一个有效算法求一个有向无环图 $G$ 的最小路径覆盖。

题解

由公式得,$DAG$ 上的最小路径覆盖 $=$ 顶点数 $-$ 其对应的二分图的最大匹配数,套上匈牙利板子即可。

  • 简要证明
    如果不匹配,那么每条路径退化为一个点,需要 $n$ 条路径才能覆盖 $n$ 个点
    每匹配一条边,就可以用一条路径覆盖原本两条路径才能覆盖的点
    归纳成功,证毕
    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
    #include <bits/stdc++.h> 
    typedef long long ll;
    const int maxn = 250;
    int mat[maxn], ans;
    bool vis[maxn];
    std::vector<int>G[maxn];
    bool dfs(int u) {
    if (vis[u]) return false; vis[u] = true;
    for (int i = G[u].size() - 1; ~i; i--) {
    int v = G[u][i];
    if (!mat[v] || dfs(mat[v])) {
    mat[v] = u; return true;
    }
    }
    return false;
    }
    int out[maxn];
    std::stack<int>s;
    int main() {
    int n, m; scanf("%d%d", &n, &m); ans = n;
    for (int i = 1; i <= m; i++) {
    int x, y; scanf("%d%d", &x, &y);
    G[x].push_back(y);
    }
    for (int i = 1; i <= n; i++) {
    memset(vis, 0, sizeof(vis));
    if (dfs(i)) ans--;
    }
    for (int i = 1; i <= n; i++) out[mat[i]]++;
    for (int i = 1; i <= n; i++) if (!out[i]) {
    for (int j = i; j; j = mat[j]) s.push(j);
    while (s.size()) printf("%d ", s.top()), s.pop();
    printf("\n");
    }
    printf("%d", ans);
    return 0;
    }

魔术球

题意

假设有 $n$ 根柱子,现要按下述规则在这 $n$ 根柱子中依次放入编号为 $1,2,3,4,⋯$ 的球。

  • 每次只能在某根柱子的最上面放球。
  • 在同一根柱子中,任何 $2$ 个相邻球的编号之和为完全平方数。

试设计一个算法,计算出在 $n$ 根柱子上最多能放多少个球。

题解

我们相当于要找到连续的一段区间 $[1, ans]$ 使得这些点可以被 $n$ 条不想交的路径覆盖掉,即在 $n$ 根柱子上,套用上一题板子即可,同样没有用到网络流,匈牙利已经足够

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
#include <bits/stdc++.h> 
typedef long long ll;
const int maxn = 2000;
int mat[maxn], ans;
std::vector<int>G[maxn];
bool in[maxn], vis[maxn];
int n;
bool dfs(int u) {
if (vis[u]) return false; vis[u] = true;
for (int i = G[u].size() - 1; ~i; i--) {
int v = G[u][i];
if (!mat[v] || dfs(mat[v])) {
mat[v] = u; return true;
}
}
if (n) return n-- | true;
return false;
}
int main() {
scanf("%d", &n);
for (int i = 1;; i++) {
for (int j = sqrt(i); j * j < i << 1; j++) {
if (j * j <= i) continue;
int k = j * j - i; G[i].push_back(k);
}
memset(vis, 0, sizeof(bool) * (i + 1));
if (!dfs(i)) n--; if (n < 0) break; ans = i;
}
printf("%d\n", ans);
for (int i = 1; i <= ans; i++)
in[mat[i]] = true;
for (int i = 1; i <= ans; i++) if (!in[i]) {
for (int j = i; j; j = mat[j])
printf("%d ", j); puts("");
}
return 0;
}

太空飞行计划

题意

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合 $E={E1,E2,⋯,Em}$ ,和进行这些实验需要使用的全部仪器的集合 $I={I1,I2,⋯,In}$ 。实验 $E_j$ 需要用到的仪器是 $I$ 的子集 $R_j⊆I$。

配置仪器 $I_k$ 的费用为 $c_k$ 美元。实验 $E_j$ 的赞助商已同意为该实验结果支付 $p_j$ 美元。$W$ 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。

题解

将这些事件想象成为一些带有权值的点,点权为正代表收益,为负代表花费,点与点之间有一些边,代表了一些依赖关系,只有当一个点所依赖的点全部被选择了之后,这个点才可以被选择,那么怎样选择才能使所选的点权和最大呢?
将点按照点权的正负划分为两个集合,权值为正的向源点 $S$ 连边,权值为负的向汇点 $T$ 连边,边权都为点权的绝对值,对于依赖关系,就连边权 $inf$ 的边,然后先假定 $ans$ 为所有正点权的和,减去 $S->T$ 的最大流即为最终答案。

这到底是在干什么?

  • 这便是经典的最大权闭合子图的网络流模型的解决方法。

为什么这样是对的?

  • 上面的操作,相当于先不管三七二十一,获取在没有限制条件下的最佳答案,然后一一解决由于依赖关系产生的矛盾,在这些矛盾中,我们可以选择放弃之前已经选择的正权点(割掉正权点与 $S$ 之间的边),也可以选择一些不得不选的负权点(割掉负权点与 $T$ 之间的边),当 $S$ 与 $T$ 不连通时,我们已经花费了最小(最小割-最大流定理)的代价,解决了所有的矛盾,所以将最初记录的最佳答案减去为了解决矛盾的花费,即为最终答案

如何输出方案?

  • 只需在最后查看一下 $deep$ 数组中不为 $0$ 的点有哪些,即最后一次分层图中能够访问到的点即可。
  • 简要证明:能够访问到的点,说明与源点 $S$ 连通,显然,对于放弃了的正权点,我们割掉的其与源点的连边,故访问不到,对于必须选择的负权点,我们割掉的其与汇点的连边,那么其一定与源点相连,证毕
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
#include <bits/stdc++.h> 
namespace MaxFlow {
const int maxm = 1e5 + 10;
const int maxn = 1e4 + 10;
const int inf = 1e9;
struct edge {
int to, next, cap;
edge() {}
edge(int x, int y, int z) {
to = x; next = y; cap = z;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
int deep[maxn];
void add(int x, int y, int w) {
e[++edgeCnt] = edge(y, head[x], w); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0); head[y] = edgeCnt;
}
bool bfs(int s, int t) {
memset(deep, 0, sizeof(int) * (t + 1));
std::queue<int>q; q.push(s); deep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v]) continue;
deep[v] = deep[u] + 1;
//if (deep[t]) return true;
q.push(v);
}
}
return deep[t];
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v] != deep[u] + 1) continue;
int a = dfs(v, t, std::min(f, e[i].cap));
r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
}
return r;
}
int dinic(int s, int t) {
int r = 0;
while (bfs(s, t))
r += dfs(s, t, inf);
return r;
}
const int maxs = 1e5;
char s[maxs]; int now = 0, ans = 0;
int read() {
int u = 0; bool f = false;
for (;!isdigit(s[now]) && s[now]; now++) if (s[now] == '-') f = true;
for (; isdigit(s[now]) && s[now]; now++) u = u * 10 + s[now] - '0';
return f ? -u : u;
}
void solve() {
#define S (n + m + 1)
#define T (n + m + 2)
int m, n; scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++) {
int x; scanf("%d", &x);
add(S, i, x); ans += x;
gets(s); now = 0;
while (x = read())
add(i, x + m, inf);
}
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x); add(i + m, T, x);
}
ans -= dinic(S, T);
for (int i = 1; i <= m; i++)
if (deep[i]) printf("%d ", i);
printf("\n");
for (int i = 1; i <= n; i++)
if (deep[i + m]) printf("%d ", i);
printf("\n%d\n", ans);
}

}

int main() {
MaxFlow::solve();
}
/*
input
2 3
10 1 2
25 2 3
50 6 7
output
2
2 3
12
*/

圆桌聚餐

题意

假设有来自 $n$ 个不同单位的代表参加一次国际会议。每个单位的代表数分别为 $r_i$。会议餐厅共有 $m$ 张餐桌,每张餐桌可容纳 $c_i$ 个代表就餐。
为了使代表们充分交流,希望从同一个单位来的代表不在同一个餐桌就餐。

试设计一个算法,给出满足要求的代表就餐方案。

题解

板子懒得打了,套用了上一题的板子水过了
比较明显的建图,每个单位向每张桌子连容量为 $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
#include <bits/stdc++.h> 

namespace MaxFlow {
const int maxm = 1e5 + 10;
const int maxn = 1e4 + 10;
const int inf = 1e9;
struct edge {
int to, next, cap;
edge() {}
edge(int x, int y, int z) {
to = x; next = y; cap = z;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
int deep[maxn];
void add(int x, int y, int w) {
e[++edgeCnt] = edge(y, head[x], w); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0); head[y] = edgeCnt;
}
bool bfs(int s, int t) {
memset(deep, 0, sizeof(int) * (t + 1));
std::queue<int>q; q.push(s); deep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v]) continue;
deep[v] = deep[u] + 1;
//if (deep[t]) return true;
q.push(v);
}
}
return deep[t];
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v] != deep[u] + 1) continue;
int a = dfs(v, t, std::min(f, e[i].cap));
r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
}
return r;
}
int dinic(int s, int t) {
int r = 0;
while (bfs(s, t))
r += dfs(s, t, inf);
return r;
}
void solve() {
#define S (n + m + 1)
#define T (n + m + 2)
int m, n, tot = 0; scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++) {
int x; scanf("%d", &x); tot += x;
add(S, i, x);
for (int j = 1; j <= n; j++)
add(i, j + m, 1);
}
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x); add(i + m, T, x);
}
if (dinic(S, T) != tot) return void(printf("0\n"));
printf("1\n");
for (int i = 1; i <= m; i++) {
for (int j = head[i]; j; j = e[j].next) {
int v = e[j].to;
if (e[j].cap) continue;
printf("%d ", v - m);
}
printf("\n");
}
}
}
int main() {
MaxFlow::solve();
}

试题库

题意

假设一个试题库中有 $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
#include <bits/stdc++.h> 

namespace MaxFlow {
const int maxm = 1e5 + 10;
const int maxn = 1e4 + 10;
const int inf = 1e9;
struct edge {
int to, next, cap;
edge() {}
edge(int x, int y, int z) {
to = x; next = y; cap = z;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
int deep[maxn];
void add(int x, int y, int w) {
e[++edgeCnt] = edge(y, head[x], w); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0); head[y] = edgeCnt;
}
bool bfs(int s, int t) {
memset(deep, 0, sizeof(int) * (t + 1));
std::queue<int>q; q.push(s); deep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v]) continue;
deep[v] = deep[u] + 1;
//if (deep[t]) return true;
q.push(v);
}
}
return deep[t];
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v] != deep[u] + 1) continue;
int a = dfs(v, t, std::min(f, e[i].cap));
r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
}
return r;
}
int dinic(int s, int t) {
int r = 0;
while (bfs(s, t))
r += dfs(s, t, inf);
return r;
}
void solve() {
#define S (n + k + 1)
#define T (n + k + 2)
int k, n, m = 0; scanf("%d%d", &k, &n);
for (int i = 1; i <= k; i++) {
int x; scanf("%d", &x); m += x; add(S, i, x);
}
for (int i = 1; i <= n; i++) {
int p, x; scanf("%d", &p);
while (p--) {
scanf("%d", &x);
add(x, i + k, 1);
}
add(i + k, T, 1);
}
if (dinic(S, T) != m) return void(printf("No Solution!"));
for (int i = 1; i <= k; i++) {
printf("%d: ", i);
for (int j = head[i]; j; j = e[j].next) {
int v = e[j].to;
if (e[j].cap || v == S) continue;
printf("%d ", v - k);
}
printf("\n");
}
}
}
int main() {
MaxFlow::solve();
}

骑士共存问题

题意

在一个 $n×n$ 个方格的国际象棋棋盘上,马(骑士)可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍,骑士不得进入。

对于给定的 $n×n$ 个方格的国际象棋棋盘和障碍标志,计算棋盘上最多可以放置多少个骑士,使得它们彼此互不攻击。

题解

观察发现棋盘是个二分图,然后水过

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
#include <bits/stdc++.h>
namespace MaxFlow {
const int maxm = 4e5 + 10;
const int maxn = 4e4 + 10;
const int inf = 1e9;
struct edge {
int to, next, cap;
edge() {}
edge(int x, int y, int z) {
to = x; next = y; cap = z;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
int deep[maxn];
void add(int x, int y, int w) {
e[++edgeCnt] = edge(y, head[x], w); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0); head[y] = edgeCnt;
}
bool bfs(int s, int t) {
memset(deep, 0, sizeof(int) * (t + 1));
std::queue<int>q; q.push(s); deep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v]) continue;
deep[v] = deep[u] + 1;
if (deep[t]) return true; q.push(v);
}
}
return false;
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v] != deep[u] + 1) continue;
int a = dfs(v, t, std::min(f, e[i].cap));
r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
}
if (!r) deep[u] = 0; return r;
}
int dinic(int s, int t) {
int r = 0;
while (bfs(s, t))
r += dfs(s, t, inf);
return r;
}
int dx[]{-2, -2, -1, -1, 1, 1, 2, 2}, dy[]{1, -1, 2, -2, 2, -2, 1, -1};
bool mmp[210][210];
#define P(i, j) (i - 1) * n + j
#define S n * n + 1
#define T n * n + 2
void solve() {
int n, m; scanf("%d%d", &n, &m);
while (m--) {
int x, y; scanf("%d%d", &x, &y);
mmp[x][y] = true;
}
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (!mmp[i][j]) {
if ((i ^ j) & 1) {
add(S, P(i, j), 1);
for (int k = 0; k < 8; k++) {
int x = i + dx[k], y = j + dy[k];
if (x < 1 || x > n || y < 1 || y > n || mmp[x][y]) continue;
add(P(i, j), P(x, y), inf);
}
}
else
add(P(i, j), T, 1);
ans++;
}
printf("%d\n", ans - dinic(S, T));
}
}
int main() {
MaxFlow::solve();
}

餐巾计划

题意

一个餐厅在相继的 $n$ 天里,每天需用的餐巾数不尽相同。假设第 $i$ 天需要 $r_i$ 块餐巾。餐厅可以购买新的餐巾,每块餐巾的费用为 $P$ 分;或者把旧餐巾送到快洗部,洗一块需 $M$ 天,其费用为 $F$ 分;或者送到慢洗部,洗一块需 $N$ 天,其费用为 $S$ 分($S < F$)。

每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。

试设计一个算法为餐厅合理地安排好 $n$ 天中餐巾使用计划,使总的花费最小。

题解

对于最小费用最大流的题,首先保证流量充足,然后再要求费用最小,我们不妨将脏的餐巾看作源点那一侧($x_i$),干净的那一侧连汇点($y_i$)
三种免费的情况

  • $S->x_i$ 容量为 $R_i$,费用为 $0$,代表每天会免费得到那么多的脏餐巾
  • $y_i->T$ 容量为 $R_i$,费用为 $0$,代表每天需要有那么多的干净餐巾被用掉
  • $x_i->x->x_i+1$ 容量为 $inf$,费用为 $0$, 代表每天可以将任意多的脏餐巾免费留到下一天
    三种付费的情况
  • $S->y_i$ 容量为 $inf$,费用为 $P$,代表每天可以以 $P$ 的单价获得任意多的干净餐巾
  • $x_i->y_i+M$ 容量为 $inf$,费用为 $F$,代表每天可以以 $F$ 的单价获清洗任意多的餐巾以供M天后使用(快洗)
  • $x_i->y_i+N$ 容量为 $inf$,费用为 $S$,代表每天可以以 $S$ 的单价获清洗任意多的餐巾以供N天后使用(慢洗)
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
#include <bits/stdc++.h>
namespace MinCostMaxFlow {
const int maxm = 2e5;
const int maxn = 2e4;
const int inf = 1e9;
struct edge {
int to, next, cap, dis;
edge(){}
edge(int x, int y, int z, int w) {
to = x; next = y; cap = z; dis = w;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
void add(int x, int y, int c, int d) {
e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
}
int dis[maxn]; bool inq[maxn], vis[maxn];
bool spfa(int s, int t) {
memset(dis, -1, sizeof(int) * (t + 1));
//memset(dis, -1, sizeof(dis));
std::queue<int>q; q.push(t); dis[t] = 0;
while (q.size()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; if (!e[i ^ 1].cap) continue;
if (!~dis[v] || dis[v] > dis[u] + e[i ^ 1].dis) {
dis[v] = dis[u] + e[i ^ 1].dis;
if (!inq[v]) inq[v] = true, q.push(v);
}
}
}
return dis[s] != -1;
}
int dfs(int u, int t, int f) {
vis[u] = true; if (u == t || !f) return f; int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to; if (!e[i].cap || vis[v]) continue;
if (dis[v] != dis[u] - e[i].dis) continue;
int a = dfs(v, t, std::min(e[i].cap, f));
e[i].cap -= a; e[i ^ 1].cap += a; f -= a; r += a;
}
if (!r) dis[u] = -1; return r;
}
std::pair<int,int> zkw(int s, int t) {
int flow = 0, cost = 0, tmp;
while (spfa(s, t)) {
memset(vis, false, sizeof(bool) * (t + 1));
tmp = dfs(s, t, inf);
flow += tmp; cost += tmp * dis[s];
}
return std::make_pair(flow, cost);
}
int r[1010];
void solve() {
int n, P, M, F, N, S; scanf("%d%d%d%d%d%d", &n, &P, &M, &F, &N, &S);
int s = (n + 1) << 1, t = s + 1;
for (int i = 1; i <= n; i++) {
scanf("%d", &r[i]);
add(s, i << 1, r[i], 0);
add(i << 1 | 1, t, r[i], 0);
add(s, i << 1 | 1, inf, P);
if (i + 1 <= n) add(i << 1, (i + 1) << 1, inf, 0);
if (i + M <= n) add(i << 1, (i + M) << 1 | 1, inf, F);
if (i + N <= n) add(i << 1, (i + N) << 1 | 1, inf, S);
}
printf("%d\n", zkw(s, t).second);
}
}
int main() {
MinCostMaxFlow::solve();
}

航空路线问题

题意

给定一张航空图,图中顶点代表城市,边代表两个城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。

  • 从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。
  • 除起点城市外,任何城市只能访问一次。

对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。

题解

即求出两条从左到右路径,使其长度和最大,且路径不相交,那么建图跑流量为 $2$ 的费用流即可,每个点拆开来限流,容量为 $1$ 代表只能走一次,费用为 $1$ 代表通过了一个城市,最后跑一边最大费用流即可,输出方案我比较笨,就打了两个 $dfs$ 走容量为不为满的边

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
#include <bits/stdc++.h>
const int oo = 1e9;
namespace MinCostMaxFlow {
const int maxn = 1e4, maxm = 1e5;
struct edge {
int to, next, cap, dis;
edge(int x = 0, int y = 0, int z = 0, int w = 0) {
to = x; next = y; cap = z; dis = w;
}
}e[maxm << 1];
int head[maxn], edgeCnt = 1;
void add(int x, int y, int c, int d) {
e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
}
int dis[maxn]; bool vis[maxn], inq[maxn];
bool bfs(int s, int t) {
memset(dis, -1, sizeof(int) * (t + 1));
std::queue<int>q; q.push(t); dis[t] = 0;
while (q.size()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; if (!e[i ^ 1].cap) continue;
if (!~dis[v] || dis[v] < dis[u] + e[i ^ 1].dis) {
dis[v] = dis[u] + e[i ^ 1].dis;
if (!inq[v]) inq[v] = true, q.push(v);
}
}
}
return dis[s] != -1;
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0; vis[u] = true;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to; if (!e[i].cap || vis[v]) continue;
if (dis[v] != dis[u] - e[i].dis) continue;
int a = dfs(v, t, std::min(f, e[i].cap));
r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
}
return r;
}
std::pair<int, int> zkw(int s, int t) {
int flow = 0, cost = 0, tmp;
while (bfs(s, t)) {
do {
tmp = dfs(s, t, oo);
memset(vis, false, sizeof(bool) * (t + 1));
flow += tmp; cost += tmp * dis[s];
}while (tmp);
}
return std::make_pair(flow, cost);
}
#define I(x) ((x) << 1)
#define O(x) ((x) << 1 | 1)
#define S I(1)
#define T O(N)
std::map<std::string, int>f;
std::vector<std::string>s(1);
void dfs1(int u, int t, int c) {
if (u == O(u >> 1))
std::cout << s[u >> 1] << std::endl;
if (u == t) return;
for (int i = head[u]; i; i = e[i].next) if (e[i].cap != oo) {
int v = e[i].to; if (v == c) continue;
if (u == I(u >> 1) && v != O(u >> 1)) continue;
dfs1(v, t, u);
e[i].cap++; e[i ^ 1].cap--;
return;
}
}
void dfs2(int u, int t, int c) {
if (u == t) return;
for (int i = head[u]; i; i = e[i].next) if (e[i].cap != oo) {
int v = e[i].to; if (v == c) continue;
if (u == I(u >> 1) && v != O(u >> 1)) continue;
dfs2(v, t, u);
if (u == O(u >> 1))
std::cout << s[u >> 1] << std::endl;
return;
}
}
void solve() {
int N, V; scanf("%d%d", &N, &V);
for (int i = 1; i <= N; i++) {
std::string tmp;
std::cin >> tmp;
int id = s.size();
f[tmp] = id;
s.push_back(tmp);
add(I(id), O(id), 1, 0);
}
while (V--) {
std::string tmp;
std::cin >> tmp;
int u = f[tmp];
std::cin >> tmp;
int v = f[tmp];
if (u > v) std::swap(u, v);
add(O(u), I(v), oo, 1);
}
add(S, O(1), 1, 0); add(I(N), T, 1, 0);
std::pair<int, int>ans = zkw(S, T);
if (ans.first != 2) return void(printf("No Solution!"));
printf("%d\n", ans.second);
dfs1(S, T, 0);
dfs2(S, T, 0);
}
}
int main() {
MinCostMaxFlow::solve();
}

分配问题

题意

有 $n$ 件工作要分配给 $n$ 个人做。第 $i$ 个人做第 $j$ 件工作产生的效益为 $c_{ij}$ 。试设计一个将 $n$ 件工作分配给 $n$ 个人做的分配方案,使产生的总效益最大/小。

题解

费用流求带权匹配,费用即为权值,最小权值直接求,最大权值将费用取负数,跑一边再取负数输出

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
#include <bits/stdc++.h>
const int oo = 1e9;
namespace MinCostMaxFlow {
const int maxn = 1e4, maxm = 1e5;
struct edge {
int to, next, cap, dis;
edge(int x = 0, int y = 0, int z = 0, int w = 0) {
to = x; next = y; cap = z; dis = w;
}
}e[maxm << 1];
int head[maxn], edgeCnt = 1;
void add(int x, int y, int c, int d) {
e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
}
int dis[maxn]; bool vis[maxn], inq[maxn];
bool bfs(int s, int t) {
for (int i = 0; i <= t; i++) dis[i] = oo;
std::queue<int>q; q.push(t); dis[t] = 0;
while (q.size()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; if (!e[i ^ 1].cap) continue;
if (dis[v] > dis[u] + e[i ^ 1].dis) {
dis[v] = dis[u] + e[i ^ 1].dis;
if (!inq[v]) inq[v] = true, q.push(v);
}
}
}
return dis[s] != oo;
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0; vis[u] = true;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to; if (!e[i].cap || vis[v]) continue;
if (dis[v] != dis[u] - e[i].dis) continue;
int a = dfs(v, t, std::min(f, e[i].cap));
r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
}
return r;
}
std::pair<int, int> zkw(int s, int t) {
int flow = 0, cost = 0, tmp;
while (bfs(s, t)) {
do {
tmp = dfs(s, t, oo);
memset(vis, false, sizeof(bool) * (t + 1));
flow += tmp; cost += tmp * dis[s];
}while (tmp);
}
return std::make_pair(flow, cost);
}
void clear() {
edgeCnt = 1;
memset(head, 0, sizeof(head));
}
int c[120][120];
void solve() {
#define S ((n + 1) << 1)
#define T (S | 1)
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
scanf("%d", &c[i][j]);
add(i << 1, j << 1 | 1, 1, c[i][j]);
}
for (int i = 1; i <= n; i++)
add(S, i << 1, 1, 0),
add(i << 1 | 1, T, 1, 0);
printf("%d\n", zkw(S, T).second);
clear();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
add(i << 1, j << 1 | 1, 1, -c[i][j]);
}
for (int i = 1; i <= n; i++)
add(S, i << 1, 1, 0),
add(i << 1 | 1, T, 1, 0);
printf("%d\n", -zkw(S, T).second);
}
}
int main() {
MinCostMaxFlow::solve();
}

星际转移

题意

由于人类对自然资源的消耗,人们意识到大约在 $2300$ 年之后,地球就不能再居住了。于是在月球上建立了新的绿地,以便在需要时移民。令人意想不到的是,$2177$ 年冬由于未知的原因,地球环境发生了连锁崩溃,人类必须在最短的时间内迁往月球。

现有 $n$ 个太空站位于地球与月球之间,且有 $m$ 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人,而每艘太空船 $i$ 只可容纳 $H_i$ 个人。每艘太空船将周期性地停靠一系列的太空站,例如:${1, 3, 4}$ 表示该太空船将周期性地停靠太空站 134134134 …

每一艘太空船从一个太空站驶往任一太空站耗时均为 $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
#include <bits/stdc++.h>
const int oo = 1e9;
namespace MaxFlow {
const int maxm = 1e5 + 10;
const int maxn = 1e4 + 10;
struct edge {
int to, next, cap;
edge() {}
edge(int x, int y, int z) {
to = x; next = y; cap = z;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
int deep[maxn];
void add(int x, int y, int w) {
e[++edgeCnt] = edge(y, head[x], w); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0); head[y] = edgeCnt;
}
bool bfs(int s, int t, int n) {
memset(deep, 0, sizeof(int) * (n + 1));
std::queue<int>q; q.push(s); deep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v]) continue;
deep[v] = deep[u] + 1; q.push(v);
}
}
return deep[t];
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v] != deep[u] + 1) continue;
int a = dfs(v, t, std::min(f, e[i].cap));
r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
}
return r;
}
int dinic(int s, int t, int n) {
int r = 0;
while (bfs(s, t, n))
r += dfs(s, t, oo);
return r;
}
struct mergefindSet {
int fa[maxn];
void clear(int n) { for (int i = 0; i <= n; i++) fa[i] = i; }
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }
}Set;
int S[50][50], T[50], N[50], H[50];
void solve() {
int n, m, k; scanf("%d%d%d", &n, &m, &k);
Set.clear(n + 2);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &H[i], &T[i]);
for (int j = 0; j < T[i]; j++) {
scanf("%d", &S[i][j]);
if (S[i][j] == 0) S[i][j] = n + 1;
if (S[i][j] ==-1) S[i][j] = n + 2;
Set.merge(S[i][0], S[i][j]);
}
}
if (Set.find(n + 1) != Set.find(n + 2)) return void(puts("0"));
int s = n + 1, t = n + 2, ans = 0;
while (k > 0) {
ans++;
add((ans - 1) * (n + 2) + s, ans * (n + 2) + s, oo);
add(ans * (n + 2) + t, (ans - 1) * (n + 2) + t, oo);
for (int i = 1; i <= m; i++) {
int u = (ans - 1) * (n + 2) + S[i][N[i]];
N[i]++; N[i] %= T[i];
int v = ans * (n + 2) + S[i][N[i]];
add(u, v, H[i]);
}
for (int i = 1; i <= n; i++)
add((ans - 1) * (n + 2) + i, ans * (n + 2) + i, oo);
k -= dinic(s, t, ans * (n + 2));
}
printf("%d\n", ans);
}
}

int main() {
MaxFlow::solve();
}
/*
input
2 2 2
2 3 0 1 2
1 3 1 2 -1
output
8
*/

软件补丁

题意

某公司发现其研制的一个软件中有 $n$ 个错误,随即为该软件发放了一批共 $m$ 个补丁程序。每一个补丁程序都有其特定的适用环境,某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时,往往会加入另一些错误。

换句话说,对于每一个补丁 $i$,都有 $2$ 个与之相应的错误集合 $B_1(i)$) 和 $B_2(i)$ ,使得仅当软件包含 $B_1(i)$ 中的所有错误,而不包含 $B_2(i)$ 中的任何错误时,才可以使用补丁 $i$。补丁 $i$ 将修复软件中的某些错误 $F_1(i)$,而同时加入另一些错误 $F_2(i)$。另外,每个补丁都耗费一定的时间。

试设计一个算法,利用公司提供的 $m$ 个补丁程序将原软件修复成一个没有错误的软件,并使修复后的软件耗时最少。

题解

$SPFA$? 好像有什么奇怪的东西混进来了。。。。

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
typedef long long ll;
int dis[1 << 20];
bool inq[1 << 20];
struct edge {
int B1, B2, F1, F2, T;
}e[120];
char s[30];
void calc(int &p, int &m) {
for (int i = 0; s[i]; i++) {
if (s[i] == '+') p |= (1 << i);
if (s[i] == '-') m |= (1 << i);
}
}
std::queue<int>q;
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d", &e[i].T);
scanf("%s", s); calc(e[i].B1, e[i].B2);
scanf("%s", s); calc(e[i].F2, e[i].F1);
}

memset(dis, -1, sizeof(dis));
q.push((1 << n) - 1); dis[(1 << n) - 1] = 0;
while (q.size()) {
int now = q.front(); q.pop(); inq[now] = false;
for (int i = 1; i <= m; i++)
if ((now | e[i].B1) == now && (now | e[i].B2) == now + e[i].B2) {
int nxt = (now - (now & e[i].F1)) | e[i].F2;
if (!~dis[nxt] || dis[nxt] > dis[now] + e[i].T) {
dis[nxt] = dis[now] + e[i].T;
if (!inq[nxt]) inq[nxt] = true, q.push(nxt);
}
}
}
printf("%d\n", dis[0] == -1 ? 0 : dis[0]);
}

汽车加油行驶问题

题意

给定一个 $\text{N}\times \text{N}$ 的方形网格,设其左上角为起点◎,坐标为 $\text{(1,1)}$ ,$\text{X}$ 轴向右为正, $\text{Y}$ 轴向下为正,每个方格边长为 $1$ ,如图所示。
一辆汽车从起点◎出发驶向右下角终点▲,其坐标为 $(\text{N},\text{N})$ 。
在若干个网格交叉点处,设置了油库,可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则:

  • 汽车只能沿网格边行驶,装满油后能行驶 $\text{K}$ 条网格边。出发时汽车已装满油,在起 点与终点处不设油库。
  • 汽车经过一条网格边时,若其 $\text{X}$ 坐标或 $\text{Y}$ 坐标减小,则应付费用 $\text{B}$ ,否则免付费用。
  • 汽车在行驶过程中遇油库则应加满油并付加油费用 $\text{A}$。
  • 在需要时可在网格点处增设油库,并付增设油库费用 $\text{C}$ (不含加油费用 $\text{A}$)。
  • $N , K , A , B , C$ 均为正整数, 且满足约束: $2\leq \text{N} \leq 100, 2 \leq \text{K} \leq 10$。

设计一个算法,求出汽车从起点出发到达终点的一条所付费用最少的行驶路线。

题解

将位置和剩余油量作为状态,跑最短路即可

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
typedef long long ll;
const int oo = 1e9;
int dis[101][101][11];
bool inq[101][101][11];
bool mp[101][101];
struct node {
int x, y, c;
node (int X = 0, int Y = 0, int C = 0) {
x = X; y = Y; c = C;
}
};
std::queue<node>q;
int dx[]{1, 0, -1, 0}, dy[]{0, 1, 0, -1};
int main() {
int n, k, a, b, c; scanf("%d%d%d%d%d", &n, &k, &a, &b, &c);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
int x; scanf("%d", &x); mp[i][j] = x;
}
memset(dis, -1, sizeof(dis));
q.push(node(1, 1, k)); dis[1][1][k] = 0;
while (q.size()) {
node now = q.front(); q.pop();
inq[now.x][now.y][now.c] = false;
if (!now.c) continue;
for (int i = 0; i < 4; i++) {
int x = now.x + dx[i], y = now.y + dy[i], B = (i & 2) ? b : 0;
if (x < 1 || y < 1 || x > n || y > n) continue;
if (mp[x][y]) {
node nxt = node(x, y, k);
if (!~dis[x][y][k] || dis[x][y][k] > dis[now.x][now.y][now.c] + a + B) {
dis[x][y][k] = dis[now.x][now.y][now.c] + a + B;
if (!inq[x][y][k]) inq[x][y][k] = true, q.push(nxt);
}
}
else {
node nxt = node(x, y, k);
if (!~dis[x][y][k] || dis[x][y][k] > dis[now.x][now.y][now.c] + a + B + c) {
dis[x][y][k] = dis[now.x][now.y][now.c] + a + B + c;
if (!inq[x][y][k]) inq[x][y][k] = true, q.push(nxt);
}
nxt = node(x, y, now.c - 1);
if (!~dis[x][y][nxt.c] || dis[x][y][nxt.c] > dis[now.x][now.y][now.c] + B) {
dis[x][y][nxt.c] = dis[now.x][now.y][now.c] + B;
if (!inq[x][y][nxt.c]) inq[x][y][nxt.c] = true, q.push(nxt);
}
}
}
}
int ans = oo;
for (int i = 0; i <= k; i++) if (~dis[n][n][i]) ans = std::min(ans, dis[n][n][i]);
printf("%d\n", ans);
return 0;
}

数字梯形

题意

给定一个由 $n$ 行数字组成的数字梯形如下图所示。梯形的第一行有 $m$ 个数字。从梯形的顶部的 $m$ 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

分别遵守以下规则:

  • 从梯形的顶至底的 $m$ 条路径互不相交;
  • 从梯形的顶至底的 $m$ 条路径仅在数字结点处相交;
  • 从梯形的顶至底的 $m$ 条路径允许在数字结点相交或边相交。

题解

  • 第一问,拆点为边,费用为数值,所有边容量为 $1$
  • 第二问,拆点为边,费用为数值,容量为正无穷,其他边容量为 $1$
  • 第三问,拆点为边,费用为数值,除了与起点相连的边容量为 $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
    #include <bits/stdc++.h> 
    namespace MaxCostMaxFlow {
    const int maxm = 1e5;
    const int maxn = 1e4;
    const int oo = 1e9;
    struct edge {
    int to, next, cap, dis;
    edge(int x = 0, int y = 0, int c = 0, int d = 0) {
    to = x; next = y; cap = c; dis = d;
    }
    }e[maxm];
    int head[maxn], edgeCnt = 1;
    void add(int x, int y, int c, int d) {
    e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
    e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
    }
    void clear() {
    edgeCnt = 1; memset(head, 0, sizeof(head));
    }
    bool inq[maxn], vis[maxn]; int dis[maxn];
    bool bfs(int s, int t) {
    memset(dis, -1, sizeof(int) * (t + 1));
    std::queue<int>q; q.push(t); dis[t] = 0;
    while (q.size()) {
    int u = q.front(); q.pop(); inq[u] = false;
    for (int i = head[u]; i; i = e[i].next) {
    if (!e[i ^ 1].cap) continue;
    int v = e[i].to;
    if (!~dis[v] || dis[v] < dis[u] + e[i ^ 1].dis) {
    dis[v] = dis[u] + e[i ^ 1].dis;
    if (!inq[v]) inq[v] = true, q.push(v);
    }
    }
    }
    return dis[s] != -1;
    }
    int dfs(int u, int t, int f) {
    if (u == t || !f) return f;
    int r = 0; vis[u] = true;
    for (int i = head[u]; i && f; i = e[i].next) {
    if (!e[i].cap) continue; int v = e[i].to;
    if (vis[v] || dis[u] - e[i].dis != dis[v]) continue;
    int a = dfs(v, t, std::min(f, e[i].cap));
    r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
    }
    if (!r) dis[u] = -1; return r;
    }
    std::pair<int,int>zkw(int s, int t) {
    int flow = 0, cost = 0, tmp;
    while (bfs(s, t)) {
    do {
    tmp = dfs(s, t, oo);
    flow += tmp;
    cost += tmp * dis[s];
    memset(vis, false, sizeof(bool) * (t + 1));
    }while (tmp);
    }
    return std::make_pair(flow, cost);
    }
    int a[50][50], b[50][50], idCnt;
    void solve() {
    int n, m; scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i + m - 1; j++) {
    b[i][j] = ++idCnt;
    scanf("%d", &a[i][j]);
    }
    }
    #define S (idCnt << 1) + 2
    #define T S + 1
    #define I(x) (x << 1)
    #define O(x) (x << 1 | 1)
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i + m - 1; j++) {
    add(I(b[i][j]), O(b[i][j]), 1, a[i][j]);
    if (i != n) add(O(b[i][j]), I(b[i + 1][j]), 1, 0);
    if (i != n) add(O(b[i][j]), I(b[i + 1][j + 1]), 1, 0);
    }
    for (int i = 1; i <= m; i++) add(S, I(b[1][i]), 1, 0);
    for (int i = 1; i <= m + n - 1; i++) add(O(b[n][i]), T, 1, 0);
    printf("%d\n", zkw(S, T).second);
    clear();
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i + m - 1; j++) {
    add(I(b[i][j]), O(b[i][j]), oo, a[i][j]);
    if (i != n) add(O(b[i][j]), I(b[i + 1][j]), 1, 0);
    if (i != n) add(O(b[i][j]), I(b[i + 1][j + 1]), 1, 0);
    }
    for (int i = 1; i <= m; i++) add(S, I(b[1][i]), 1, 0);
    for (int i = 1; i <= m + n - 1; i++) add(O(b[n][i]), T, oo, 0);
    printf("%d\n", zkw(S, T).second);
    clear();
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i + m - 1; j++) {
    add(I(b[i][j]), O(b[i][j]), oo, a[i][j]);
    if (i != n) add(O(b[i][j]), I(b[i + 1][j]), oo, 0);
    if (i != n) add(O(b[i][j]), I(b[i + 1][j + 1]), oo, 0);
    }
    for (int i = 1; i <= m; i++) add(S, I(b[1][i]), 1, 0);
    for (int i = 1; i <= m + n - 1; i++) add(O(b[n][i]), T, oo, 0);
    printf("%d\n", zkw(S, T).second);
    }
    }
    int main() {
    MaxCostMaxFlow::solve();
    }

最长递增子序列

题意

给定正整数序列 x1∼xn x_1 \sim x_n x​1​​∼x​n​​,以下递增子序列均为非严格递增。

  • 计算其最长递增子序列的长度 $s$。
  • 计算从给定的序列中最多可取出多少个长度为 $s$ 的递增子序列。
  • 如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$,则从给定序列中最多可取出多少个长度为 $s$ 的递增子序列。

    题解

    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
    #include <bits/stdc++.h> 
    namespace MaxFlow {
    const int maxm = 1e5 + 10;
    const int maxn = 1e3 + 10;
    const int oo = 1e9;
    struct edge {
    int to, next, cap;
    edge() {}
    edge(int x, int y, int z) {
    to = x; next = y; cap = z;
    }
    }e[maxm];
    int head[maxn], edgeCnt = 1;
    int deep[maxn];
    void add(int x, int y, int w) {
    e[++edgeCnt] = edge(y, head[x], w); head[x] = edgeCnt;
    e[++edgeCnt] = edge(x, head[y], 0); head[y] = edgeCnt;
    }
    bool bfs(int s, int t) {
    memset(deep, 0, sizeof(int) * (t + 1));
    std::queue<int>q; q.push(s); deep[s] = 1;
    while (q.size()) {
    int u = q.front(); q.pop();
    for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (!e[i].cap || deep[v]) continue;
    deep[v] = deep[u] + 1; q.push(v);
    }
    }
    return deep[t];
    }
    int dfs(int u, int t, int f) {
    if (u == t || !f) return f;
    int r = 0;
    for (int i = head[u]; i && f; i = e[i].next) {
    int v = e[i].to;
    if (!e[i].cap || deep[v] != deep[u] + 1) continue;
    int a = dfs(v, t, std::min(f, e[i].cap));
    r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
    }
    if (!r) deep[u] = -1; return r;
    }
    int dinic(int s, int t) {
    int r = 0;
    while (bfs(s, t))
    r += dfs(s, t, oo);
    return r;
    }
    void clear() {
    edgeCnt = 1; memset(head, 0, sizeof(head));
    }
    int n, a[maxn], f[maxn], g[maxn];
    void solve() {
    #define S ((n + 1) << 1)
    #define T ((n + 2) << 1)
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) {
    if (!g[0] || g[g[0]] <= a[i]) g[++g[0]] = a[i], f[i] = g[0];
    else {
    int *p = std::upper_bound(g + 1, g + 1 + g[0], a[i]);
    f[i] = p - g; *p = a[i];
    }
    }
    printf("%d\n", g[0]);
    for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++)
    if (f[j] == f[i] + 1 && a[j] >= a[i])
    add(i << 1 | 1, j << 1, 1);
    if (f[i] == 1) add(S, i << 1, 1);
    if (f[i] == g[0]) add(i << 1 | 1, T, 1);
    add(i << 1, i << 1 | 1, 1);
    }
    printf("%d\n", dinic(S, T));
    clear();
    for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++)
    if (f[j] == f[i] + 1 && a[j] >= a[i])
    add(i << 1 | 1, j << 1, 1);
    if (f[i] == 1) add(S, i << 1, 1);
    if (f[i] == g[0]) add(i << 1 | 1, T, 1);
    add(i << 1, i << 1 | 1, (i == 1 || i == n) ? oo : 1);
    }
    add(S, 1 << 1, oo); if (f[n] == g[0]) add(n << 1 | 1, T, oo);
    printf("%d\n", dinic(S, T));
    }
    }
    int main() {
    MaxFlow::solve();
    }

方格取数

题意

在一个有 $m \times n$ 个方格的棋盘中,每个方格中有一个正整数。

现要从方格中取数,使任意 $2$ 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。

题解

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
#include <bits/stdc++.h> 
namespace MaxFlow {
const int maxm = 1e5 + 10;
const int maxn = 1e3 + 10;
const int oo = 1e9;
struct edge {
int to, next, cap;
edge() {}
edge(int x, int y, int z) {
to = x; next = y; cap = z;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
int deep[maxn];
void add(int x, int y, int w) {
e[++edgeCnt] = edge(y, head[x], w); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0); head[y] = edgeCnt;
}
bool bfs(int s, int t) {
memset(deep, 0, sizeof(int) * (t + 1));
std::queue<int>q; q.push(s); deep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v]) continue;
deep[v] = deep[u] + 1; q.push(v);
}
}
return deep[t];
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v] != deep[u] + 1) continue;
int a = dfs(v, t, std::min(f, e[i].cap));
r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
}
if (!r) deep[u] = -1; return r;
}
int dinic(int s, int t) {
int r = 0;
while (bfs(s, t))
r += dfs(s, t, oo);
return r;
}
void clear() {
edgeCnt = 1; memset(head, 0, sizeof(head));
}
int a[50][50], ans, dx[]{0, 0, 1, -1}, dy[]{1, -1, 0, 0};
#define P(i, j) (i - 1) * m + j
#define S (n * m + 1)
#define T (n * m + 2)

void solve() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &a[i][j]), ans += a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if ((i ^ j) & 1) {
add(S, P(i, j), a[i][j]);
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (x < 1 || y < 1 || x > n || y > m) continue;
add(P(i, j), P(x, y), oo);
}
}
else add(P(i, j), T, a[i][j]);
}
printf("%d\n", ans - dinic(S, T));
}
}
int main() {
MaxFlow::solve();
}

运输问题

题意

$W$ 公司有 $m$ 个仓库和 $n$ 个零售商店。第 $i$ 个仓库有 $a_i$ 个单位的货物;第 $j$ 个零售商店需要 $b_j$ 个单位的货物。货物供需平衡,即 $\sum\limits_{i = 1} ^ m a_i = \sum\limits_{j = 1} ^ n b_j$。从第 $i$ 个仓库运送每单位货物到第 $j$ 个零售商店的费用为 $c_{ij}$。试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少。

题解

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
#include <bits/stdc++.h> 
namespace MinCostMaxFlow {
const int maxm = 2e5;
const int maxn = 2e4;
const int oo = 1e9;
struct edge {
int to, next, cap, dis;
edge(){}
edge(int x, int y, int z, int w) {
to = x; next = y; cap = z; dis = w;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
void add(int x, int y, int c, int d) {
e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
}
int dis[maxn]; bool inq[maxn], vis[maxn];
bool spfa(int s, int t) {
for (int i = 0; i <= t; i++) dis[i] = oo;
//memset(dis, -1, sizeof(dis));
std::queue<int>q; q.push(t); dis[t] = 0;
while (q.size()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; if (!e[i ^ 1].cap) continue;
if (dis[v] > dis[u] + e[i ^ 1].dis) {
dis[v] = dis[u] + e[i ^ 1].dis;
if (!inq[v]) inq[v] = true, q.push(v);
}
}
}
return dis[s] != oo;
}
int dfs(int u, int t, int f) {
vis[u] = true; if (u == t || !f) return f; int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to; if (!e[i].cap || vis[v]) continue;
if (dis[v] != dis[u] - e[i].dis) continue;
int a = dfs(v, t, std::min(e[i].cap, f));
e[i].cap -= a; e[i ^ 1].cap += a; f -= a; r += a;
}
return r;
}
std::pair<int,int> zkw(int s, int t) {
int flow = 0, cost = 0, tmp;
while (spfa(s, t)) {
do {
memset(vis, false, sizeof(vis));
tmp = dfs(s, t, oo);
flow += tmp; cost += tmp * dis[s];
}while (tmp);
}
return std::make_pair(flow, cost);
}
void clear() {
edgeCnt = 1; memset(head, 0, sizeof(head));
}
int a[maxn], b[maxn], c[120][120];
void solve() {
#define S (n + m + 1)
#define T (n + m + 2)
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
add(S, i, a[i], 0);
}
for (int i = 1; i <= m; i++) {
scanf("%d", &b[i]);
add(i + n, T, b[i], 0);
}
for (int i = 1; i <= n; i++)
for (int j = 1 ; j <= m; j++) {
scanf("%d", &c[i][j]);
add(i, j + n, oo, c[i][j]);
}
printf("%d\n", zkw(S, T).second);
clear();
for (int i = 1; i <= n; i++)
add(S, i, a[i], 0);
for (int i = 1; i <= m; i++)
add(i + n, T, b[i], 0);
for (int i = 1; i <= n; i++)
for (int j = 1 ; j <= m; j++)
add(i, j + n, oo, -c[i][j]);
printf("%d\n", -zkw(S, T).second);
}
}
int main() {
MinCostMaxFlow::solve();
}

负载平衡

题意

$G$ 公司有 $n$ 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 $n$ 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。

题解

相信做到了这里的同学早就会了怎么建图,附上代码,不多赘述。

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
#include <bits/stdc++.h> 
namespace MinCostMaxFlow {
const int maxm = 2e5;
const int maxn = 2e4;
const int oo = 1e9;
struct edge {
int to, next, cap, dis;
edge(){}
edge(int x, int y, int z, int w) {
to = x; next = y; cap = z; dis = w;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
void add(int x, int y, int c, int d) {
e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
}
int dis[maxn]; bool inq[maxn], vis[maxn];
bool spfa(int s, int t) {
for (int i = 0; i <= t; i++) dis[i] = oo;
//memset(dis, -1, sizeof(dis));
std::queue<int>q; q.push(t); dis[t] = 0;
while (q.size()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; if (!e[i ^ 1].cap) continue;
if (dis[v] > dis[u] + e[i ^ 1].dis) {
dis[v] = dis[u] + e[i ^ 1].dis;
if (!inq[v]) inq[v] = true, q.push(v);
}
}
}
return dis[s] != oo;
}
int dfs(int u, int t, int f) {
vis[u] = true; if (u == t || !f) return f; int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to; if (!e[i].cap || vis[v]) continue;
if (dis[v] != dis[u] - e[i].dis) continue;
int a = dfs(v, t, std::min(e[i].cap, f));
e[i].cap -= a; e[i ^ 1].cap += a; f -= a; r += a;
}
return r;
}
std::pair<int,int> zkw(int s, int t) {
int flow = 0, cost = 0, tmp;
while (spfa(s, t)) {
do {
memset(vis, false, sizeof(vis));
tmp = dfs(s, t, oo);
flow += tmp; cost += tmp * dis[s];
}while (tmp);
}
return std::make_pair(flow, cost);
}
void clear() {
edgeCnt = 1; memset(head, 0, sizeof(head));
}
int a[maxn], sum;
void solve() {
#define S n + 1
#define T n + 2
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), sum += a[i];
sum /= n;
for (int i = 1; i <= n; i++) {
if (a[i] > sum) add(S, i, a[i] - sum, 0);
if (a[i] < sum) add(i, T, sum - a[i], 0);
int r = i % n + 1, l = (((i - 1) % n) + n - 1) % n + 1;
add(i, l, oo, 1); add(i, r, oo, 1);
}
printf("%d\n", zkw(S, T).second);
}
}
int main() {
MinCostMaxFlow::solve();
}

最长 $k$ 可重区间集

题意

给定实直线 $L$ 上 $n$ 个开区间组成的集合 $I$,和一个正整数 $k$,试设计一个算法,从开区间集合 $I$ 中选取出开区间集合 $S \subseteq I$,使得在实直线 $L$ 的任何一点 $x$,$S$ 中包含点 $x$ 的开区间个数不超过 $k$。且 $\sum\limits_{z \in S} | z |$ 达到最大。这样的集合 $S$ 称为开区间集合 $I$ 的最长 $k$ 可重区间集。$\sum\limits_{z \in S} | z |$ 称为最长 $k$ 可重区间集的长度。

对于给定的开区间集合 $I$ 和正整数 $k$,计算开区间集合 $I$ 的最长 $k$ 可重区间集的长度。

题解

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
#include <bits/stdc++.h> 
namespace MinCostMaxFlow {
const int maxm = 1e6;
const int maxn = 2e3;
const int oo = 1e9;
struct edge {
int to, next, cap, dis;
edge(){}
edge(int x, int y, int z, int w) {
to = x; next = y; cap = z; dis = w;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
void add(int x, int y, int c, int d) {
e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
}
int dis[maxn]; bool inq[maxn], vis[maxn];
bool spfa(int s, int t) {
for (int i = 0; i <= t; i++) dis[i] = oo;
//memset(dis, -1, sizeof(dis));
std::queue<int>q; q.push(t); dis[t] = 0;
while (q.size()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; if (!e[i ^ 1].cap) continue;
if (dis[v] > dis[u] + e[i ^ 1].dis) {
dis[v] = dis[u] + e[i ^ 1].dis;
if (!inq[v]) inq[v] = true, q.push(v);
}
}
}
return dis[s] != oo;
}
int dfs(int u, int t, int f) {
vis[u] = true; if (u == t || !f) return f; int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to; if (!e[i].cap || vis[v]) continue;
if (dis[v] != dis[u] - e[i].dis) continue;
int a = dfs(v, t, std::min(e[i].cap, f));
e[i].cap -= a; e[i ^ 1].cap += a; f -= a; r += a;
}
return r;
}
std::pair<int,int> zkw(int s, int t) {
int flow = 0, cost = 0, tmp;
while (spfa(s, t)) {
do {
memset(vis, false, sizeof(vis));
tmp = dfs(s, t, oo);
flow += tmp; cost += tmp * dis[s];
}while (tmp);
}
return std::make_pair(flow, cost);
}
void clear() {
edgeCnt = 1; memset(head, 0, sizeof(head));
}
std::pair<int,int>line[maxn];
void solve() {
int n, k; scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &line[i].first, &line[i].second);
if (line[i].first > line[i].second)
std::swap(line[i].first, line[i].second);
}
sort(line + 1, line + 1 + n);
int S = (n + 1) << 1, T = (n + 1) << 1 | 1;
add(S, 1, k, 0);
for (int i = 1; i <= n; i++) {
add(1, i << 1, oo, 0); add(i << 1 | 1, T, oo, 0);
add(i << 1, i << 1 | 1, 1, line[i].first - line[i].second);
for (int j = i + 1; j <= n; j++) {
if (line[j].first >= line[i].second)
add(i << 1 | 1, j << 1, oo, 0);
}
}
printf("%d\n", -zkw(S, T).second);
}
}
int main() {
MinCostMaxFlow::solve();;
}

孤岛营救问题

题意

$1944$年,特种兵麦克接到国防部的命令,要求立即赶赴太平洋上的一个孤岛,营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里,迷宫地形复杂,但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形,其南北方向被划分为 $n$ 行,东西方向被划分为 $m$ 列, 于是整个迷宫被划分为 $n \times m$ 个单元。每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。南北或东西方向相邻的 $2$ 个单元之间可能互通,也可能有一扇锁着的门,或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙,并且所有的门被分成 $p$ 类, 打开同一类的门的钥匙相同,不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角,即 $(n,m)$ 单元里,并已经昏迷。迷宫只有一个入口, 在西北角。也就是说,麦克可以直接进入 $(1,1)$ 单元。另外,麦克从一个单元移动到另一个 相邻单元的时间为 $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
#include <bits/stdc++.h> 
const int oo = 1e9;
int key[20][20];
int dis[12][12][1 << 10];
bool iq[12][12][1 << 10];
struct edge {
int tx, ty, key;
edge(int x = 0, int y = 0, int z = 0) {
tx = x; ty = y; key = z;
}
};
std::vector<edge>G[20][20];
void addedge(int x1, int y1, int x2, int y2, int g) {
if (!g) {
bool find = false;
for (int i = 0; i < G[x1][y1].size(); i++) {
edge &e = G[x1][y1][i];
if (e.tx == x2 && e.ty == y2) find = true;
}
if (!find) G[x1][y1].push_back(edge(x2, y2, 0));
}
else if (!~g) {
bool find = false;
for (int i = 0; i < G[x1][y1].size(); i++) {
edge &e = G[x1][y1][i];
if (e.tx == x2 && e.ty == y2) {
e.key = -1; find = true;
}
}
if (!find) G[x1][y1].push_back(edge(x2, y2, -1));
}
else {
bool find = false;
for (int i = 0; i < G[x1][y1].size(); i++) {
edge &e = G[x1][y1][i];
if (e.tx == x2 && e.ty == y2) {
if (e.key != -1) e.key |= 1 << (g - 1); find = true;
}
}
if (!find) G[x1][y1].push_back(edge(x2, y2, 1 << (g - 1)));
}
}
struct state {
int x, y, z;
state(){}
state(int x, int y, int z) : x(x), y(y), z(z) {}
};
std::queue<state>que;
int dx[]{0, 0, -1, 1}, dy[]{1, -1, 0, 0};
int main() {
int n, m, p; scanf("%d%d%d", &n, &m, &p);
int k; scanf("%d", &k);
while (k--) {
int x1, y1, x2, y2, g;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &g);
addedge(x1, y1, x2, y2, g == 0 ? -1 : g);
addedge(x2, y2, x1, y1, g == 0 ? -1 : g);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int l = 0; l < 4; l++) {
int x = i + dx[l], y = j + dy[l];
if (x < 1 || y < 1 || x > n || y > m) continue;
addedge(i, j, x, y, 0);
}
int s; scanf("%d", &s);
while (s--) {
int x, y, q; scanf("%d%d%d", &x, &y, &q);
key[x][y] |= 1 << (q - 1);
}
memset(dis, -1, sizeof(dis));
que.push(state(1, 1, key[1][1]));
dis[1][1][key[1][1]] = 0;
while (que.size()) {
state now = que.front(); que.pop(); iq[now.x][now.y][now.z] = false;
for (int i = G[now.x][now.y].size() - 1; ~i; i--) {
edge &e = G[now.x][now.y][i]; if (e.key == -1) continue;
state nxt(e.tx, e.ty, now.z | key[e.tx][e.ty]);
if ((e.key & now.z) != e.key) continue;
if (!~dis[nxt.x][nxt.y][nxt.z] ||
dis[nxt.x][nxt.y][nxt.z] > dis[now.x][now.y][now.z] + 1) {
dis[nxt.x][nxt.y][nxt.z] = dis[now.x][now.y][now.z] + 1;
if (!iq[nxt.x][nxt.y][nxt.z]) iq[nxt.x][nxt.y][nxt.z] = true, que.push(nxt);
}

}
}
int ans = oo;
for (int i = 0; i < 1 << p; i++)
if (dis[n][m][i] != -1)
ans = std::min(ans, dis[n][m][i]);
printf("%d\n", ans == oo ? -1 : ans);
}

深海机器人问题

题意

深海资源考察探险队的潜艇将到达深海的海底进行科学考察。
潜艇内有多个深海机器人。潜艇到达深海海底后,深海机器人将离开潜艇向预定目标移动。
深海机器人在移动中还必须沿途采集海底生物标本。沿途生物标本由最先遇到它的深海机器人完成采集。
每条预定路径上的生物标本的价值是已知的,而且生物标本只能被采集一次。
本题限定深海机器人只能从其出发位置沿着向北或向东的方向移动,而且多个深海机器人可以在同一时间占据同一位置。
用一个 $\text{P} \times \text{Q}$ 网格表示深海机器人的可移动位置。西南角的坐标为 $(0,0)$ ,东北角的坐标为 $(Q,P)$ 。
给定每个深海机器人的出发位置和目标位置,以及每条网格边上生物标本的价值。
计算深海机器人的最优移动方案, 使深海机器人到达目的地后,采集到的生物标本的总价值最高。

题解

照着描述建图即可,不多说

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
#include <bits/stdc++.h> 
namespace MinCostMaxFlow {
const int maxm = 2e5;
const int maxn = 1e4;
const int oo = 1e9;
struct edge {
int to, next, cap, dis;
edge(){}
edge(int x, int y, int z, int w) {
to = x; next = y; cap = z; dis = w;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
void add(int x, int y, int c, int d) {
e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
}
int dis[maxn]; bool inq[maxn], vis[maxn];
bool spfa(int s, int t) {
for (int i = 0; i <= t; i++) dis[i] = oo;
//memset(dis, -1, sizeof(dis));
std::queue<int>q; q.push(t); dis[t] = 0;
while (q.size()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; if (!e[i ^ 1].cap) continue;
if (!~dis[v] || dis[v] > dis[u] + e[i ^ 1].dis) {
dis[v] = dis[u] + e[i ^ 1].dis;
if (!inq[v]) inq[v] = true, q.push(v);
}
}
}
return dis[s] != oo;
}
int dfs(int u, int t, int f) {
vis[u] = true; if (u == t || !f) return f; int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to; if (!e[i].cap || vis[v]) continue;
if (dis[v] != dis[u] - e[i].dis) continue;
int a = dfs(v, t, std::min(e[i].cap, f));
e[i].cap -= a; e[i ^ 1].cap += a; f -= a; r += a;
}
if (!r) dis[u] = oo; return r;
}
std::pair<int,int> zkw(int s, int t) {
int flow = 0, cost = 0, tmp;
while (spfa(s, t)) {
do {
memset(vis, false, sizeof(vis));
tmp = dfs(s, t, oo);
flow += tmp; cost += tmp * dis[s];
}while (tmp);
}
return std::make_pair(flow, cost);
}
#define ID(i, j) ((i) * (Q + 1) + j)
#define S ID(P, Q) + 1
#define T S + 1
void solve() {
int a, b, P, Q; scanf("%d%d%d%d", &a, &b, &P, &Q);
for (int i = 0; i <= P; i++)
for (int j = 1; j <= Q; j++) {
int x; scanf("%d", &x);
add(ID(i, j - 1), ID(i, j), 1, -x);
add(ID(i, j - 1), ID(i, j), oo, 0);
}
for (int j = 0; j <= Q; j++)
for (int i = 1; i <= P; i++) {
int x; scanf("%d", &x);
add(ID(i - 1, j), ID(i, j), 1, -x);
add(ID(i - 1, j), ID(i, j), oo, 0);
}
while (a--) {
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
add(S, ID(x, y), k, 0);
}
while (b--) {
int k, x, y;
scanf("%d%d%d", &k, &x, &y);
add(ID(x, y), T, k, 0);
}
printf("%d\n", -zkw(S, T).second);
}
}
int main() {
MinCostMaxFlow::solve();
}

最长 $k$ 可重线段集问题

题意

给定平面 $\text{xoy}$上 $n$ 个开线段组成的集合 $\text{I}$,和一个正整数 $k$,试设计一个算法。
从开线段集合$\text{I}$中选取出开线段集合$\text{S}\in \text{I}$ ,
使得在x轴上的任何一点 $\text{p}$ , $\text{S}$ 中与直线 $\text{x}=\text{p}$ 相交的开线段个数不超过 $\text{k}$ ,
且 $\sum_{\text{z} \in \text{S}}|z|$ 达到最大。
这样的集合 $\text{S}$ 称为开线段集合$\text{I}$ 的最长 $\text{k}$ 可重线段集的长度。
对于任何开线段$\text{z}$ ,设其断电坐标为$( x_0 , y_0 )$和 $( x_1 , y_1 )$,
则开线段 $\text{z}$ 的长度 $|\text{z}|$定义为: $|z| = \lfloor \sqrt{ ( x_1 - x_0 ) ^ 2 + ( y_1 - y_0 )^2 } \rfloor$
对于给定的开线段集合 $\text{I}$ 和正整数 $\text{k}$ ,计算开线段集合 $\text{I}$ 的最长 $\text{k}$ 可重线段集的长度。

题解

注意两点

  • 求线段长度时中间过程可能爆掉 $int$
  • 对于竖直的线段,会占据当前横坐标

剩下就和「最长 $k$ 可重区间集」一样了

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
#include <bits/stdc++.h> 
typedef long long ll;
namespace MinCostMaxFlow {
const int maxm = 2e6;
const int maxn = 1e4;
const int oo = 1e9;
struct edge {
int to, next, cap, dis;
edge(){}
edge(int x, int y, int z, int w) {
to = x; next = y; cap = z; dis = w;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
void add(int x, int y, int c, int d) {
e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
}
int dis[maxn]; bool inq[maxn], vis[maxn];
bool spfa(int s, int t) {
for (int i = 0; i <= t; i++) dis[i] = oo;
//memset(dis, -1, sizeof(dis));
std::queue<int>q; q.push(t); dis[t] = 0;
while (q.size()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; if (!e[i ^ 1].cap) continue;
if (!~dis[v] || dis[v] > dis[u] + e[i ^ 1].dis) {
dis[v] = dis[u] + e[i ^ 1].dis;
if (!inq[v]) inq[v] = true, q.push(v);
}
}
}
return dis[s] != oo;
}
int dfs(int u, int t, int f) {
vis[u] = true; if (u == t || !f) return f; int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to; if (!e[i].cap || vis[v]) continue;
if (dis[v] != dis[u] - e[i].dis) continue;
int a = dfs(v, t, std::min(e[i].cap, f));
e[i].cap -= a; e[i ^ 1].cap += a; f -= a; r += a;
}
if (!r) dis[u] = oo; return r;
}
std::pair<int,int> zkw(int s, int t) {
int flow = 0, cost = 0, tmp;
while (spfa(s, t)) {
do {
memset(vis, false, sizeof(vis));
tmp = dfs(s, t, oo);
flow += tmp; cost += tmp * dis[s];
}while (tmp);
}
return std::make_pair(flow, cost);
}
struct Line {
int x1, x2, y1, y2;
}l[maxn];
bool cmp(Line a, Line b) {
return a.x1 < b.x1;
}
void solve() {
#define S ((n + 1) << 1)
#define T ((n + 1) << 1 | 1)
int n, k; scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d%d", &l[i].x1, &l[i].y1, &l[i].x2, &l[i].y2);
if (l[i].x1 > l[i].x2) std::swap(l[i].x1, l[i].x2), std::swap(l[i].y1, l[i].y2);
}
std::sort(l + 1, l + 1 + n, cmp);
for (int i = 1; i <= n; i++) {
int v = sqrt(((ll)l[i].x1 - l[i].x2) * (l[i].x1 - l[i].x2) + ((ll)l[i].y1 - l[i].y2) * (l[i].y1 - l[i].y2));
add(i << 1, i << 1 | 1, 1, -v);
for (int j = i + 1; j <= n; j++) {
if (l[j].x1 < l[i].x2) continue;
if (l[i].x1 == l[i].x2 && l[j].x1 == l[j].x2 && l[i].x1 == l[j].x1) continue;
add(i << 1 | 1, j << 1, 1, 0);
}
add(1, i << 1, 1, 0); add(i << 1 | 1, T, 1, 0);
}
add(S, 1, k, 0);
printf("%d\n", -zkw(S, T).second);
}
}
int main() {
MinCostMaxFlow::solve();
}

火星探险问题

题意

火星探险队的登陆舱将在火星表面着陆,登陆舱内有多部障碍物探测车。
登陆舱着陆后,探测车将离开登陆舱向先期到达的传送器方向移动。
探测车在移动中还必须采集岩石标本。
每一块岩石标本由最先遇到它的探测车完成采集。
每块岩石标本只能被采集一次。
岩石标本被采集后,其他探测车可以从原来岩石标本所在处通过。
探测车不能通过有障碍的地面。
本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动,而且多个探测车可以在同一时间占据同一位置。
如果某个探测车在到达传送器以前不能继续前进,则该车所采集的岩石标本将全部损失。
用一个 $\text{P}\times \text{Q}$ 网格表示登陆舱与传送器之间的位置。登陆舱的位置在 $(X_1,Y_1)​​​$ 处,传送器 的位置在 $(X_P,Y_Q)$ 处。 给定每个位置的状态,计算探测车的最优移动方案,使到达传送器的探测车的数量最多, 而且探测车采集到的岩石标本的数量最多。

题解

此题 $P$, $Q$ 怎么感觉跟我平常打的程序是反着的。。。大致就是先跑遍费用流,然后循环 $car$ 次,跟着流量走,不走回头路即可

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> 
typedef long long ll;
namespace MinCostMaxFlow {
const int maxm = 2e6;
const int maxn = 1e4;
const int oo = 1e9;
struct edge {
int to, next, cap, dis;
edge(){}
edge(int x, int y, int z, int w) {
to = x; next = y; cap = z; dis = w;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
void add(int x, int y, int c, int d) {
e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
}
int dis[maxn]; bool inq[maxn], vis[maxn];
bool spfa(int s, int t) {
for (int i = 0; i <= t; i++) dis[i] = oo;
//memset(dis, -1, sizeof(dis));
std::queue<int>q; q.push(t); dis[t] = 0;
while (q.size()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; if (!e[i ^ 1].cap) continue;
if (dis[v] > dis[u] + e[i ^ 1].dis) {
dis[v] = dis[u] + e[i ^ 1].dis;
if (!inq[v]) inq[v] = true, q.push(v);
}
}
}
return dis[s] != oo;
}
int dfs(int u, int t, int f) {
vis[u] = true; if (u == t || !f) return f; int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to; if (!e[i].cap || vis[v]) continue;
if (dis[v] != dis[u] - e[i].dis) continue;
int a = dfs(v, t, std::min(e[i].cap, f));
e[i].cap -= a; e[i ^ 1].cap += a; f -= a; r += a;
}
if (!r) dis[u] = oo; return r;
}
std::pair<int,int> zkw(int s, int t) {
int flow = 0, cost = 0, tmp;
while (spfa(s, t)) {
do {
memset(vis, false, sizeof(vis));
tmp = dfs(s, t, oo);
flow += tmp; cost += tmp * dis[s];
}while (tmp);
}
return std::make_pair(flow, cost);
}
int mp[50][50], car, P, Q;
#define ID(i, j) ((i - 1) * Q + j)
#define S ((ID(P, Q) + 1) << 1)
#define T ((ID(P, Q) + 1) << 1 | 1)
void print(int id, int u, int f) {
int x1 = ((u >> 1) + Q - 1) / Q, y1 = ((u >> 1) + Q - 1) % Q + 1;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (e[i].cap == oo) continue;
if (v == f) continue;
if (v >> 1 == u >> 1) {
e[i].cap++; e[i ^ 1].cap--;
print(id, v, u); return;
}
if (u == S) {
e[i].cap++; e[i ^ 1].cap--;
print(id, v, u); return;
}
if (v == T) {
e[i].cap++; e[i ^ 1].cap--; return;
}
int x2 = ((v >> 1) + Q - 1) / Q, y2 = ((v >> 1) + Q - 1) % Q + 1;
if (x2 < x1 || y2 < y1) continue;
if (x1 + 1 == x2) {
printf("%d 0\n", id);
e[i].cap++; e[i ^ 1].cap--;
print(id, v, u); return;
}
if (y1 + 1 == y2) {
printf("%d 1\n", id);
e[i].cap++; e[i ^ 1].cap--;
print(id, v, u); return;
}
}
}
void solve() {
scanf("%d%d%d", &car, &Q, &P);
for (int i = 1; i <= P; i++)
for (int j = 1; j <= Q; j++)
scanf("%d", &mp[i][j]);
for (int i = 1; i <= P; i++) {
for (int j = 1; j <= Q; j++) {
if (mp[i][j] == 1) continue;
if (mp[i][j] == 2)
add(ID(i, j) << 1, ID(i, j) << 1 | 1, 1, -1);
add(ID(i, j) << 1, ID(i, j) << 1 | 1, oo, 0);
if (i != P && mp[i + 1][j] != 1) add(ID(i, j) << 1 | 1, ID(i + 1, j) << 1, oo, 0);
if (j != Q && mp[i][j + 1] != 1) add(ID(i, j) << 1 | 1, ID(i, j + 1) << 1, oo, 0);
}
}
add(S, ID(1, 1) << 1, car, 0);
add(ID(P, Q) << 1 | 1, T, car, 0);
std::pair<int,int>ans = zkw(S, T);
//printf("%d %d\n", ans.first, -ans.second);
for (int i = 1; i <= car; i++) print(i, S, 0);
}
}
int main() {
MinCostMaxFlow::solve();
}