2019/11/27 洛谷开坑

2019/12/6 完结

飞行员配对方案问题

https://www.luogu.com.cn/problem/P2756

简单二分图匹配,匈牙利算法即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 10;
int V;
vector<int>G[maxn];
int match[maxn];
bool used[maxn];
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
bool dfs(int v) {
used[v] = 1;
for (int i = 0; i < G[v].size(); i++) {
int u = G[v][i], w = match[u];
if (w < 0 || !used[w] && dfs(w)) {
match[v] = u;
match[u] = v;
return true;
}
}
return false;
}
int bi_match() {
int res = 0;
memset(match, -1, sizeof(match));
for (int v = 1; v <= V; v++) {
if (match[v] < 0) {
memset(used, 0, sizeof(used));
if (dfs(v)) {
res++;
}
}
}
return res;
}
int n, m;
int main() {
scanf("%d%d", &m, &n);
V = n + m;
int u, v;
while (scanf("%d%d", &u, &v) && u != -1) {
G[u].push_back(v);
G[v].push_back(u);
}
int ans = bi_match();
if (ans == 0)printf("No Solution!\n");
else {
printf("%d\n", ans);
for (int i = 1; i <= V; i++) {
if (match[i] != -1) {
printf("%d %d\n", i, match[i]);
match[match[i]] = -1;
}
}
}
return 0;
}

 

圆桌问题

https://www.luogu.com.cn/problem/P3254

简单建图

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 10;
int n, m;
int a, b;
int s, t;
struct Edge
{
int from, to, cap, flow;
};
vector<Edge>edges;
vector<int>G[maxn];
void add_edge(int from, int to, int cap) {
edges.push_back(Edge{ from,to,cap,0 });
edges.push_back(Edge{ to,from,0,0 });
m = (int)edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool vis[maxn];
int d[maxn], cur[maxn];
bool bfs() {
memset(vis, 0, sizeof(vis));
queue<int>Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while (!Q.empty()) {
int x = Q.front(); Q.pop();
for (int i = 0; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x, int a) {
if (x == t || a == 0)return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0)break;
}
}
return flow;
}
int maxflow(int s, int t) {
int flow = 0;
while (bfs()) {
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
int main() {
scanf("%d%d", &a, &b);
s = 0, t = a + b + 1;
for (int i = 1; i <= a; i++) {
int u;
scanf("%d", &u);
n += u;
add_edge(s, i, u);
}
for (int i = 1; i <= b; i++) {
int u;
scanf("%d", &u);
add_edge(i + a, t, u);
}
for (int i = 1; i <= a; i++) {
for (int j = a + 1; j <= a + b; j++) {
add_edge(i, j, 1);
}
}
int ans = maxflow(s, t);
if (ans == n) {
printf("1\n");
for (int i = 1; i <= a; i++) {
for (int j : G[i]) {
if (edges[j].flow > 0)
printf("%d ", edges[j].to - a);
}
printf("\n");
}
}
else printf("0\n");
return 0;
}

 

魔术球问题

https://www.luogu.com.cn/problem/P2765

有向图最小路径覆盖

起初我试图直接将一定范围内的边处理完,但后来发现这又涉及到路径上点的顺序问题,证明这种想法不可行。

其实柱子的个数相当于路径的个数,串起了一些点,当路径数小于 nn 时,就是可行的。

所以就一直向图里加点并从已有点向新加点连边(符合条件的前提下)。重新跑一边最小路径覆盖。直到路径数大于 nn

有向图最小路径覆盖=顶点数-拆点后最大匹配数

无向图最小路径覆盖=顶点数-拆点后最大匹配数/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
80
81
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 10;
int V;
vector<int>G[maxn];
int match[maxn];
bool used[maxn];
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
bool dfs(int v) {
used[v] = 1;
for (int i = 0; i < G[v].size(); i++) {
int u = G[v][i], w = match[u];
if (w < 0 || !used[w] && dfs(w)) {
match[v] = u;
match[u] = v;
return true;
}
}
return false;
}
int bi_match() {
int res = 0;
memset(match, -1, sizeof(match));
for (int v = 1; v <= V; v++) {
if (match[v] < 0) {
memset(used, 0, sizeof(used));
if (dfs(v)) {
res++;
}
}
}
return res;
}
int n;
vector<int>vc[maxn];
bool vis[maxn];
int main() {
scanf("%d", &n);
int ans = 1;
while (1) {
V = ans * 2;
for (int i = sqrt(ans) + 1; i*i < 2 * ans; i++) {
add_edge((i*i - ans) * 2, ans * 2 - 1);
}
if (ans - bi_match() > n)break;
ans++;
}
ans--;
for (int i = 1; i <= 2 * ans; i++)G[i].clear();
for (int i = 1; i <= ans; i++) {
for (int j = sqrt(i) + 1; j*j < 2 * i; j++) {
add_edge((j*j - i) * 2, i * 2 - 1);
}
}
bi_match();
int now = 1, cnt = 0;
while (cnt < n) {
while (vis[now])now++;
int u = now;
while (u != -1){
vis[u] = 1;
vc[cnt].push_back(u);
if (match[u * 2] == -1)break;
u = (match[u * 2] - 1) / 2 + 1;
}
cnt++;
}
printf("%d\n", ans);
for (int i = 0; i < cnt; i++) {
sort(vc[i].begin(), vc[i].end());
for (int v : vc[i])printf("%d ", v);
printf("\n");
}
return 0;
}

 

孤岛营救问题

https://www.luogu.com.cn/problem/P4011

这是网络流?

状压dp+bfs

dp[i] [j] [S]表示位于 (i,j)(i,j) 处,且拥有的钥匙集合为 SS 的状态的最小距离。

需要注意一个点可能有多个钥匙。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
typedef pair<int, pii> ppii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int N, M, P;
int K, Q;
int door[20][20][20][20];
int d[20][20][1 << 15];
int dx[]{ -1,1,0,0 };
int dy[]{ 0,0,-1,1 };
vector<int>keys[20][20];
struct X
{
int x, y, S;
int dis;
bool operator<(const X& rhs)const {
return dis > rhs.dis;
}
};
bool leg(int x,int y,int S,int nx,int ny) {
int k = door[x][y][nx][ny];
bool res = nx >= 1 && nx <= N && ny >= 1 && ny <= M && k != 0;
if (k != 0 && k != -1) {
res = res && (S&(1 << k));
}
return res;
}
int bfs(X s) {
priority_queue<X>que;
memset(d, 0x3f, sizeof(d));
que.push(s);
d[s.x][s.y][s.S] = 0;
while (!que.empty()) {
X tp = que.top(); que.pop();
int x = tp.x, y = tp.y, S = tp.S, dis = tp.dis;
if (x == N && y == M)return dis;
if (d[x][y][S] < dis)continue;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i], nS = S;
if (leg(x, y, S, nx, ny)) {
for (int p : keys[nx][ny])nS |= (1 << p);
if (d[nx][ny][nS] > d[x][y][S] + 1) {
d[nx][ny][nS] = d[x][y][S] + 1;
que.push(X{ nx,ny,nS,d[nx][ny][nS] });
}
}
}
}
return -1;
}
int main() {
scanf("%d%d%d", &N, &M, &K);
scanf("%d", &K);
memset(door, -1, sizeof(door));
for (int i = 1; i <= K; i++) {
int x1, y1, x2, y2, op;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &op);
door[x1][y1][x2][y2] = door[x2][y2][x1][y1] = op;
}
scanf("%d", &Q);
for (int i = 0; i < Q; i++) {
int x, y, op;
scanf("%d%d%d", &x, &y, &op);
keys[x][y].push_back(op);
}
X s = X{ 1,1,0,0 };
for (int p : keys[0][0])s.S &= (1 << p);
printf("%d\n", bfs(s));
return 0;
}

 

试题库问题

https://www.luogu.com.cn/problem/P2763

简单建图

以每道题和每个题型为点,加上超源,超汇,共 n+k+2n+k+2 个点,从题型向题连边,题向T连,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
98
99
100
101
102
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
typedef pair<int, pii> ppii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n, k;
int s, t;
int a[maxn];
int tot;
int m = 0;
struct Edge
{
int from, to, cap, flow;
};
vector<Edge>edges;
vector<int>G[maxn];
void add_edge(int from, int to, int cap) {
edges.push_back(Edge{ from,to,cap,0 });
edges.push_back(Edge{ to,from,0,0 });
m = (int)edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool vis[maxn];
int d[maxn], cur[maxn];
bool bfs() {
memset(vis, 0, sizeof(vis));
queue<int>Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while (!Q.empty()) {
int x = Q.front(); Q.pop();
for (int i = 0; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x, int a) {
if (x == t || a == 0)return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0)break;
}
}
return flow;
}
int maxflow(int s, int t) {
int flow = 0;
while (bfs()) {
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
int main() {
scanf("%d%d", &k, &n);
s = 0;
for (int i = 1; i <= k; i++) {
scanf("%d", &a[i]);
tot += a[i];
}
for (int i = 1; i <= k; i++) {
add_edge(s, i + n, a[i]);
}
t = n + k + 1;
for (int i = 1; i <= n; i++) {
int p;
scanf("%d", &p);
for (int j = 0; j < p; j++) {
int u;
scanf("%d", &u);
add_edge(u + n, i, 1);
}
add_edge(i, t, 1);
}
if (maxflow(s, t) != tot)printf("No Solution!\n");
else {
for (int i = 1; i <= k; i++) {
printf("%d: ", i);
for (int p : G[i + n]) {
if (edges[p].flow > 0)printf("%d ", edges[p].to);
}
printf("\n");
}
}
return 0;
}

 

火星探险问题

https://www.luogu.com.cn/problem/P3356

首先,如果第一个机器人能够从起点走到终点,那么以后的机器人也都可以。所以这就是一个费用流问题,当最大流大于0,就表示能走通,要让流过的路径上费用最大,把费用变为负数即可转化为最小费用流。

我的答案中跑了N次最大流为1的费用流,当然也可以只跑一次流量为N的费用流。

最后是取答案,找到所有有流量的正向边输出即可。循环和递归都可以。

如果是一次跑N流的话,输出时要把当前路径上的边流量-1,每次都只走流量大于0的边,这样才不会重复。

补充一下,只跑一次是在有石头的点拆点后不仅连了容量1,费用-1的边,还要和其它格子一样连一条容量为INF,费用为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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int n, m, k;
int mz[40][40];
int xy2id(int x, int y) {
return x * m + y;
}
pii id2xy(int id) {
return pii(id / m, id%m);
}
struct E
{
int from, to, cp, v;
int rev;
E() {}
E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {}
};
struct MCMF
{
int n, m, s, t;
vector<E> edges;
vector<int> G[maxn];
bool inq[maxn]; //是否在队列
int d[maxn]; //Bellman_ford单源最短路径
int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号
int a[maxn]; //a[i]表示从s到i的最小残量
void init(int _n, int _s, int _t) {
n = _n; s = _s; t = _t;
for (int i = 0; i <= n; i++) G[i].clear();
edges.clear(); m = 0;
}

void addedge(int from, int to, int cap, int cost) {
edges.push_back(E(from, to, cap, cost, 0));
edges.push_back(E(to, from, 0, -cost, 1));
G[from].push_back(m++);
G[to].push_back(m++);
}

bool BellmanFord(int &flow, int &cost) {
for (int i = 0; i <= n; i++) d[i] = INF;
memset(inq, 0, sizeof inq);
d[s] = 0, a[s] = INF, inq[s] = true;
queue<int> Q; Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for (int& idx : G[u]) {
E &e = edges[idx];
if (e.cp && d[e.to] > d[u] + e.v) {
d[e.to] = d[u] + e.v;
p[e.to] = idx;
a[e.to] = min(a[u], e.cp);
if (!inq[e.to]) {
Q.push(e.to);
inq[e.to] = true;
}
}
}
}
if (d[t] == INF) return false;
flow += a[t];
cost += a[t] * d[t];
int u = t;
while (u != s) {
edges[p[u]].cp -= a[t];
edges[p[u] ^ 1].cp += a[t];
u = edges[p[u]].from;
}
return true;
}

pii go() {
int flow = 0, cost = 0;
while (BellmanFord(flow, cost));
return pii(flow, cost);
}
} MM;
int dx[]{ 1,0 };
int dy[]{ 0,1 };
bool leg(int x, int y) {
return x >= 0 && x < n&&y >= 0 && y < m && mz[x][y] != 1;
}
bool vis[maxn];
int main() {
scanf("%d", &k);
scanf("%d%d", &m, &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &mz[i][j]);
}
}
if (mz[0][0] == 1) {
printf("0\n");
return 0;
}
int t = n * m - 1;
MM.init(n*m, n*m, t);
MM.addedge(MM.s, 0, 1, mz[0][0] == 2 ? -1 : 0);
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
if (leg(x, y)) {
int id = xy2id(x, y);
for (int i = 0; i < 2; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (leg(nx, ny)) {
MM.addedge(id, xy2id(nx, ny), 1, mz[nx][ny] == 2 ? -1 : 0);
}
}
}
}
}
for (int i = 1; i <= k; i++) {
pii p = MM.go();
if (!p.first) {
printf("0\n");
return 0;
}
else {
int u = 0;
while (u != t) {
vis[u] = 1;
pii p = id2xy(u);
int x = p.first, y = p.second;
for (int j = 0; j < MM.G[u].size(); j++) {
if (MM.edges[MM.G[u][j]].rev)continue;
if (MM.edges[MM.G[u][j]].cp == 0) {
int v = MM.edges[MM.G[u][j]].to;
u = v;
if (id2xy(v).first == x)printf("%d %d\n", i, 1);
else printf("%d %d\n", i, 0);
break;
}
}
}
vis[u] = 1;
for (int i = 0; i < MM.m; i += 2) {
if (vis[MM.edges[i].to])MM.edges[i].v = MM.edges[i + 1].v = 0;
MM.edges[i].cp = 1;
MM.edges[i + 1].cp = 0;
}
}
}
return 0;
}

 

餐巾计划问题

https://www.luogu.com.cn/problem/P1251

很容易想到拆点,虽然我也不知道为什么会想到,可能是因为不拆点做不出来?

把每个点拆成两个,但是想到之后连边还是一个问题。

有四种获得餐巾的方式,下面分别考虑。

第一种,要从源点 SS 向每天的第一个点,代表从外界买入新的餐巾,费用为 pp,容量为 INFINF

第二种,把旧餐巾送到快洗部,即可以直接连到第 mm 天后的第一个点,代表第 mm 天后可以直接使用这些干净的餐巾,费用为 ff,容量为 INFINF

第三种,把旧餐巾送到慢洗部,与快洗部处理方式相同,直接连到第 nn 天后的第一个点,费用为 ss,容量为 INFINF

第四种,把旧餐巾留到下一天,仍然是旧餐巾,所以当然不能连到下一天第一个点,否则会被当成新餐巾算入当天的流量中,而应该连到下一天的第二个点,和下一天新产生的旧餐巾混在一起处理。费用为 00,容量为 INFINF

接下来,就要考虑怎么保证每天的流量都是 r[i]r[i],所以肯定要从每天选一个点连到汇点 TT 。由于我们之前的所有处理都是把旧餐巾都连到了每天的第二个点,所以从第二个点连边的话不能保证所有流量都是干净餐巾。故要从每天的第一个点连向汇点 TT ,容量都是 r[i]r[i] ,费用为 00,当且仅当满流时符合条件。

对于每天的两个点,它们之间也要连一条边,代表当天结束后多少个新餐巾变成旧餐巾,与所有之前遗留下来的旧餐巾混在一起处理。

接下来我就发现了一个问题,由于每天的第一个点都要连出一条流量为 r[i]r[i] 的边连向汇点 TT,就会导致当天遗留下来的餐巾莫名其妙地分出去一些,无法留到当天结束,但这些餐巾又是必须要处理的,否则会白白浪费资源。所以必须要从源点 SS 处补充回来,可以发现,每次流向 TT 的边流量一定是 r[i]r[i] (因为满流),所以要从源点 SS 向每天的第二个点补充容量为 r[i]r[i],费用为 00 的边,由于这条边费用为 00,所以相比起那些费用大于 00 的边,一定会先把新加的这条边流满,就相当于补充了 r[i]r[i] 的流量。

至此,所有连边处理完了,一共连了六条边。接下来就是简单的费用流模板题。

不过我还以为费用流复杂度不是 O(NEf)O(N\cdot E\cdot f) 吗?怎么这里4000个点,最大1e7的流量能跑这么快?

更,似乎用的网络流复杂度是 O(n^3)。

注意开 long long。

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>
using namespace std;
#define ll long long
typedef pair<int, ll> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;

struct E
{
int from, to, cp, v;
E() {}
E(int f, int t, int cp, int v) :from(f), to(t), cp(cp), v(v) {}
};
struct MCMF
{
int n, m, s, t;
vector<E> edges;
vector<int> G[maxn];
bool inq[maxn]; //是否在队列
int d[maxn]; //Bellman_ford单源最短路径
int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号
int a[maxn]; //a[i]表示从s到i的最小残量
void init(int _n, int _s, int _t) {
n = _n; s = _s; t = _t;
for (int i = 0; i < n; i++) G[i].clear();
edges.clear(); m = 0;
}

void addedge(int from, int to, int cap, int cost) {
edges.push_back(E(from, to, cap, cost));
edges.push_back(E(to, from, 0, -cost));
G[from].push_back(m++);
G[to].push_back(m++);
}

bool BellmanFord(int &flow, ll &cost) {
for (int i = 0; i < n; i++) d[i] = INF;
memset(inq, 0, sizeof inq);
d[s] = 0, a[s] = INF, inq[s] = true;
queue<int> Q; Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for (int& idx : G[u]) {
E &e = edges[idx];
if (e.cp && d[e.to] > d[u] + e.v) {
d[e.to] = d[u] + e.v;
p[e.to] = idx;
a[e.to] = min(a[u], e.cp);
if (!inq[e.to]) {
Q.push(e.to);
inq[e.to] = true;
}
}
}
}
if (d[t] == INF) return false;
flow += a[t];
cost += a[t] * d[t];
int u = t;
while (u != s) {
edges[p[u]].cp -= a[t];
edges[p[u] ^ 1].cp += a[t];
u = edges[p[u]].from;
}
return true;
}

ll go() {
int flow = 0;
ll cost = 0;
while (BellmanFord(flow, cost));
return cost;
}
} MM;

int N;
int r[maxn];
ll p, m, f, n, s;
int S, T;
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &r[i]);
}
S = 2 * N, T = 2 * N + 1;
cin >> p >> m >> f >> n >> s;
MM.init(2 * N + 2, S, T);
for (int i = 0; i < N; i++) {
MM.addedge(S, 2 * i, INF, p);
MM.addedge(S, 2 * i + 1, r[i], 0);
MM.addedge(2 * i, T, r[i], 0);
if (i < N - 1) {
MM.addedge(2 * i + 1, 2 * i + 3, INF, 0);
}
if (i + m < N) {
MM.addedge(2 * i + 1, 2 * i + 2 * m, INF, f);
}
if (i + n < N) {
MM.addedge(2 * i + 1, 2 * i + 2 * n, INF, s);
}
}
int flow = 0;
cout << MM.go() << endl;
return 0;
}

 

数字梯形问题

https://www.luogu.com.cn/problem/P4013

傻逼题,纯考拆点和建图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int a[100][100];
int n, m;
struct E
{
int from, to, cp, v;
int rev;
E() {}
E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {}
};
struct MCMF
{
int n, m, s, t;
vector<E> edges;
vector<int> G[maxn];
bool inq[maxn]; //是否在队列
int d[maxn]; //Bellman_ford单源最短路径
int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号
int a[maxn]; //a[i]表示从s到i的最小残量
void init(int _n, int _s, int _t) {
n = _n; s = _s; t = _t;
for (int i = 0; i < n; i++) G[i].clear();
edges.clear(); m = 0;
}

void addedge(int from, int to, int cap, int cost) {
edges.push_back(E(from, to, cap, cost, 0));
edges.push_back(E(to, from, 0, -cost, 1));
G[from].push_back(m++);
G[to].push_back(m++);
}

bool BellmanFord(int &flow, int &cost) {
for (int i = 0; i < n; i++) d[i] = INF;
memset(inq, 0, sizeof inq);
d[s] = 0, a[s] = INF, inq[s] = true;
queue<int> Q; Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for (int& idx : G[u]) {
E &e = edges[idx];
if (e.cp && d[e.to] > d[u] + e.v) {
d[e.to] = d[u] + e.v;
p[e.to] = idx;
a[e.to] = min(a[u], e.cp);
if (!inq[e.to]) {
Q.push(e.to);
inq[e.to] = true;
}
}
}
}
if (d[t] == INF) return false;
flow += a[t];
cost += a[t] * d[t];
int u = t;
while (u != s) {
edges[p[u]].cp -= a[t];
edges[p[u] ^ 1].cp += a[t];
u = edges[p[u]].from;
}
return true;
}

pii go() {
int flow = 0, cost = 0;
while (BellmanFord(flow, cost));
return pii(cost, flow);
}
} MM;
int S, T;
int sum[30];
int xy2k(int x, int y) {
if (x == 0)return y;
return sum[x - 1] + y;
}
int main() {
scanf("%d%d", &m, &n);
sum[0] = m;
for (int i = 1; i < n; i++)sum[i] = sum[i - 1] + 1;
for (int i = 1; i < n; i++)sum[i] += sum[i - 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m + i; j++) {
scanf("%d", &a[i][j]);
}
}
int tot = (2 * m + n - 1)*n / 2;
int N = 2 * tot + 2;
S = N - 2;
T = N - 1;
MM.init(N, S, T);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m + i; j++) {
int id = xy2k(i, j);
MM.addedge(id, id + tot, 1, -a[i][j]);
if (i == n - 1)continue;
MM.addedge(id + tot, xy2k(i + 1, j), 1, 0);
MM.addedge(id + tot, xy2k(i + 1, j + 1), 1, 0);
}
}
for (int i = 0; i < m; i++) {
MM.addedge(S, i, 1, 0);
}
for (int i = 0; i < m + n - 1; i++) {
MM.addedge(xy2k(n - 1, i)+tot, T, 1, 0);
}
cout << -MM.go().first << endl;
S = tot, T = tot + 1;
MM.init(tot + 2, S, T);
for (int i = 0; i < m; i++) {
MM.addedge(S, i, 1, -a[0][i]);
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m + i; j++) {
int id = xy2k(i, j);
MM.addedge(id, xy2k(i + 1, j),1,-a[i+1][j]);
MM.addedge(id, xy2k(i + 1, j + 1), 1, -a[i + 1][j + 1]);
}
}
for (int i = 0; i < m + n - 1; i++) {
MM.addedge(xy2k(n - 1, i), T, INF, 0);
}
cout << -MM.go().first << endl;
MM.init(tot + 2, S, T);
for (int i = 0; i < m; i++) {
MM.addedge(S, i, 1, -a[0][i]);
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m + i; j++) {
int id = xy2k(i, j);
MM.addedge(id, xy2k(i + 1, j), INF, -a[i + 1][j]);
MM.addedge(id, xy2k(i + 1, j + 1), INF, -a[i + 1][j + 1]);
}
}
for (int i = 0; i < m + n - 1; i++) {
MM.addedge(xy2k(n - 1, i), T, INF, 0);
}
cout << -MM.go().first << endl;
return 0;
}

 

方格取数问题

https://www.luogu.com.cn/problem/P2774

对于每一个方格,与它周围四个格子存在冲突,所以把它和周围四个格子连边。

对于每一个方格,按照其xy坐标之和的奇偶性可分为两类,每一类内部的所有点是不会冲突的。

那么这就变成了一个二分图,问题转化为,要在所有点中选择一些点,满足这些点之间没有连边。这就是一个最小割问题,把这两类点集,一类连向S,另一类连向T,容量都为格子的值。还要在互相冲突的两个点之间连一条容量为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;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
struct mxfl
{
int n = 0;
int m = 0;
int s, t;
struct Edge
{
int from, to, cap, flow;
};
vector<Edge>edges;
vector<int>G[maxn];
void init(int _n, int _s, int _t) {
n = _n;
s = _s;
t = _t;
edges.clear();
for (int i = 0; i < n; i++)G[i].clear();
}
void add_edge(int from, int to, int cap) {
edges.push_back(Edge{ from,to,cap,0 });
edges.push_back(Edge{ to,from,0,0 });
m = (int)edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool vis[maxn];
int d[maxn], cur[maxn];
bool bfs() {
memset(vis, 0, sizeof(vis));
queue<int>Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while (!Q.empty()) {
int x = Q.front(); Q.pop();
for (int i = 0; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x, int a) {
if (x == t || a == 0)return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0)break;
}
}
return flow;
}
int maxflow() {
int flow = 0;
while (bfs()) {
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
}MF;

int n, m;
int xy2k(int x, int y) {
return x * m + y;
}
bool leg(int x, int y) {
return x >= 0 && x < n&&y >= 0 && y < m;
}
int mz[110][110];
int dx[]{ -1,1,0,0 };
int dy[]{ 0,0,-1,1 };
int ans;
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &mz[i][j]);
ans += mz[i][j];
}
}
int s = n * m, t = n * m + 1;
MF.init(n*m + 2, s, t);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int id = xy2k(i, j);
if ((i+j) & 1)MF.add_edge(id, t, mz[i][j]);
else {
MF.add_edge(s, id, mz[i][j]);
for (int k = 0; k < 4; k++) {
int nx = i + dx[k], ny = j + dy[k];
if (leg(nx, ny)) {
MF.add_edge(id, xy2k(nx, ny), INF);
}
}
}
}
}
printf("%d\n", ans - MF.maxflow());
return 0;
}

 

骑士共存问题

https://www.luogu.com.cn/problem/P3355

与方格取数问题有些类似。

容易想到这是二分图找最大独立集。

对于二分图,最大独立集=顶点数-最大匹配。

所以把所有冲突的点之间连边,同样,根据xy坐标和的奇偶性分为两个点集,保证了同一点集之内不会有连边。

本题卡了匈牙利算法,只能用Dinic。所以要分出明确的两个点集。

由于我在做这题前没做方格取数问题,所以还做了次二分图染色来分出二分图,有点蠢。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, k;
int m = 0;
int s, t;
struct Edge
{
int from, to, cap, flow;
};
vector<Edge>edges;
vector<int>G[maxn];
void add_edge(int from, int to, int cap) {
edges.push_back(Edge{ from,to,cap,0 });
edges.push_back(Edge{ to,from,0,0 });
m = (int)edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool vis[maxn];
int d[maxn], cur[maxn];
bool bfs() {
memset(vis, 0, sizeof(vis));
queue<int>Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while (!Q.empty()) {
int x = Q.front(); Q.pop();
for (int i = 0; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x, int a) {
if (x == t || a == 0)return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0)break;
}
}
return flow;
}
int maxflow(int s, int t) {
int flow = 0;
while (bfs()) {
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
bool blo[300][300];
int xy2k(int x, int y) {
return x * n + y;
}
bool leg(int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n && !blo[x][y];
}
vector<int>g[maxn];
int color[maxn];
void AddEdge(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
void pai(int u, int fa, int col) {
vis[u] = 1;
color[u] = col;
for (int v : g[u]) {
if ((!vis[v]) && v != fa){
pai(v, fa, col ^ 1);
}
}
}
int dx[]{ -1,-2,2,1,-2,-1,2,1 };
int dy[]{ 2,1,1,2,-1,-2,-1,-2 };
int main() {
scanf("%d%d", &n, &k);
s = n * n; t = n * n + 1;
for (int i = 0; i < k; i++) {
int x, y;
scanf("%d%d", &x, &y);
x--; y--;
blo[x][y] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (blo[i][j])continue;
int id = xy2k(i, j);
if (leg(i - 1, j + 2))AddEdge(id, xy2k(i - 1, j + 2));
if (leg(i - 2, j + 1))AddEdge(id, xy2k(i - 2, j + 1));
if (leg(i + 2, j + 1))AddEdge(id, xy2k(i + 2, j + 1));
if (leg(i + 1, j + 2))AddEdge(id, xy2k(i + 1, j + 2));
}
}
for (int i = 0; i < n*n; i++) {
if (!vis[i])pai(i, -1, 0);
}
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (blo[i][j])continue;
int id = xy2k(i, j);
if (color[id] == 1) {
add_edge(id, t, 1);
continue;
}
add_edge(s, id, 1);
for (int p = 0; p < 8; p++) {
int nx = i + dx[p], ny = j + dy[p];
if (leg(nx, ny))add_edge(id, xy2k(nx, ny), 1);
}
}
}
printf("%d\n", n*n - maxflow(s, t) - k);
return 0;
}

 

汽车加油行驶问题

https://www.luogu.com.cn/problem/P4009

并没有网络流。

dp+bfs

dp[i] [j] [k] 表示在坐标 (i,j)(i,j) 处,油量为 kk,的最小花费。

观察发现,在某点建立加油站后最优解不可能再次经过该点,因为再次经过时花费大于等于第一次,且油量小于等于第一次。

所以分该点是否有强制加油,此时油量是否大于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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, K, A, B, C;
int d[110][110][20];
int mz[110][110];
struct X
{
int x, y, k;
int dis;
bool operator<(const X& rhs)const {
return dis > rhs.dis;
}
};
int dx[]{ 1,0,0,-1 };
int dy[]{ 0,1,-1,0 };
bool leg(int x, int y) {
return x >= 0 && x < n&&y >= 0 && y < n;
}
void bfs() {
priority_queue<X>que;
memset(d, 0x3f, sizeof(d));
que.push(X{ 0,0,K,0 });
d[0][0][K] = 0;
while (!que.empty()) {
X tp = que.top(); que.pop();
int x = tp.x, y = tp.y, k = tp.k, dis = tp.dis;
if (d[x][y][k] < dis)continue;
if (mz[x][y] && k != K) {
if (d[x][y][K] > dis + A) {
d[x][y][K] = dis + A;
que.push(X{ x,y,K,d[x][y][K] });
}
}
else {
if (k == 0) {
if (d[x][y][K] > dis + A + C) {
d[x][y][K] = dis + A + C;
que.push(X{ x,y,K,d[x][y][K] });
}
}
else {
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i], nk = k - 1;
if (!leg(nx, ny))continue;
int ndis = dis + (i < 2 ? 0 : B);
if (d[nx][ny][nk] > ndis) {
d[nx][ny][nk] = ndis;
que.push(X{ nx,ny,nk,ndis });
}
}
}
}
}
}
int main() {
scanf("%d%d%d%d%d", &n, &K, &A, &B, &C);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &mz[i][j]);
}
}
bfs();
int ans = INF;
for (int i = 0; i <= K; i++) {
ans = min(ans, d[n - 1][n - 1][i]);
}
cout << ans << endl;
return 0;
}

 

[CTSC1999]家园

https://www.luogu.com.cn/problem/P2754

可能是这套题目里最重要的题了。

真正的分层图最大流。之前都只是分层图bfs。

根据时间分层,每过一天,就向图中添加n+2个点,并根据m个飞船的当日情况从旧的点向新的点连边。

具体来说,初始图是 n+2n+2 个孤立的点,ui,ju_{i,j} 表示第 ii 天的第 jj 个空间站,图上没有连边则表示 T=0T=0 时没有路线。第一天先向图中添加 n+2n+2 个点,若有飞船从 aabb ,则从 uT1,au_{T-1,a}uT,bu_{T,b} 连边,边容量为该飞船容量。表示当天可以新增的路线。

再对于每个空间站,从 uT1,au_{T-1,a}uT,au_{T,a} 连边,容量为 INF,表示待在原地不动。

跑一次 u0,0u_{0,0}uT,N1u_{T,N-1} 的最大流,判断若流量大于等于 kk,则可以输出答案了。

注意不要每次都重新建图,每次都可以在前一次的图上继续跑,把流量不断累加即可。

本题与《训练指南》的例题31 “Bring Them Here” 几乎是一样的。

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
typedef pair<int, int> pii;
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;

struct mxfl
{
int n = 0;
int m = 0;
int s, t;
struct Edge
{
int from, to, cap, flow;
};
vector<Edge>edges;
vector<int>G[maxn];
void init(int _n, int _s, int _t) {
n = _n;
s = _s;
t = _t;
edges.clear();
for (int i = 0; i < n; i++)G[i].clear();
}
void add_edge(int from, int to, int cap) {
edges.push_back(Edge{ from,to,cap,0 });
edges.push_back(Edge{ to,from,0,0 });
m = (int)edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool vis[maxn];
int d[maxn], cur[maxn];
bool bfs() {
memset(vis, 0, sizeof(vis));
queue<int>Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while (!Q.empty()) {
int x = Q.front(); Q.pop();
for (int i = 0; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x, int a) {
if (x == t || a == 0)return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0)break;
}
}
return flow;
}
int maxflow() {
int flow = 0;
while (bfs()) {
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
}MF;

int n, m, k, N;
int H[maxn], r[maxn];
vector<int>vc[maxn];
int pre = 0;
bool check(int t) {
for (int i = 0; i < N; i++) {
MF.add_edge(i + (t - 1)*N, i + t * N, INF);
}
for (int i = 0; i < m; i++) {
int u = vc[i][(t - 1 + r[i]) % r[i]], v = vc[i][t%r[i]];
MF.add_edge(u + (t - 1)*N, v + t * N, H[i]);
}
MF.s = 0, MF.t = N * t + (N - 1);
int nw = MF.maxflow();
if (pre + nw >= k)return true;
pre += nw;
return false;
}

int main() {
scanf("%d%d%d", &n, &m, &k);
N = n + 2;
for (int i = 0; i < m; i++) {
scanf("%d", &H[i]);
scanf("%d", &r[i]);
for (int j = 0; j < r[i]; j++) {
int x;
scanf("%d", &x);
if (x == -1)x = N - 1;
vc[i].push_back(x);
}
}
for (int t = 1; t <= 100; t++) {
if (check(t)) {
printf("%d\n", t);
return 0;
}
}
printf("0\n");
return 0;
}

 

航空路线问题

https://www.luogu.com.cn/problem/P2770

要找到两条最左到最右的路径,路径上点不重复,且经过的点最多。

则拆点后跑一次固定流量为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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int K = 2;
struct E
{
int from, to, cp, v;
int rev;
E() {}
E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {}
};
struct MCMF
{
int n, m, s, t;
vector<E> edges;
vector<int> G[maxn];
bool inq[maxn]; //是否在队列
int d[maxn]; //Bellman_ford单源最短路径
int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号
int a[maxn]; //a[i]表示从s到i的最小残量
void init(int _n, int _s, int _t) {
n = _n; s = _s; t = _t;
for (int i = 0; i < n; i++) G[i].clear();
edges.clear(); m = 0;
}

void addedge(int from, int to, int cap, int cost) {
edges.push_back(E(from, to, cap, cost, 0));
edges.push_back(E(to, from, 0, -cost, 1));
G[from].push_back(m++);
G[to].push_back(m++);
}

bool BellmanFord(int &flow, int &cost) {
for (int i = 0; i < n; i++) d[i] = INF;
memset(inq, 0, sizeof inq);
d[s] = 0, a[s] = INF, inq[s] = true;
queue<int> Q; Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for (int& idx : G[u]) {
E &e = edges[idx];
if (e.cp && d[e.to] > d[u] + e.v) {
d[e.to] = d[u] + e.v;
p[e.to] = idx;
a[e.to] = min(a[u], e.cp);
if (!inq[e.to]) {
Q.push(e.to);
inq[e.to] = true;
}
}
}
}
if (d[t] == INF) return false;
if (flow + a[t] > K)a[t] = K - flow;
flow += a[t];
cost += a[t] * d[t];
int u = t;
while (u != s) {
edges[p[u]].cp -= a[t];
edges[p[u] ^ 1].cp += a[t];
u = edges[p[u]].from;
}
if (flow == K)return false;
return true;
}

pii go() {
int flow = 0, cost = 0;
while (BellmanFord(flow, cost));
return pii(flow, cost);
}
} MM;
int n, m;
string mz[110];
map<string, int>mp;
queue<int>q;
void pr(int u) {
q.push(u/2);
for (int i : MM.G[u+1]) {
if (MM.edges[i].rev)continue;
if (MM.edges[i ^ 1].cp > 0) {
MM.edges[i ^ 1].cp--;
pr(MM.edges[i].to);
break;
}
}
}
stack<int>st;
void pr1(int u) {
st.push(u / 2);
for (int i : MM.G[u + 1]) {
if (MM.edges[i].rev)continue;
if (MM.edges[i ^ 1].cp > 0) {
MM.edges[i ^ 1].cp--;
pr1(MM.edges[i].to);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
cin >> mz[i];
mp[mz[i]] = i;
}
int S = 0, T = 2 * n - 1;
MM.init(2 * n, S, T);
for (int i = 0; i < m; i++) {
string u, v;
cin >> u >> v;
int p = mp[u], q = mp[v];
if (p > q)swap(p, q);
MM.addedge(p * 2 + 1, q * 2, INF, -1);
}
for (int i = 1; i < n - 1; i++) {
MM.addedge(i * 2, i * 2 + 1, 1, 0);
}
MM.addedge(0, 1, 2, 0); MM.addedge(2 * n - 2, 2 * n - 1, 2, 0);
pii ans = MM.go();
if (ans.first < 2) {
cout << "No Solution!" << endl;
return 0;
}
cout << -ans.second << endl;
pr(0);
while (!q.empty()) {
cout << mz[q.front()] << endl;
q.pop();
}
pr1(0);
st.pop();
while (!st.empty()) {
cout << mz[st.top()] << endl;
st.pop();
}
return 0;
}

 

太空飞行计划问题

https://www.luogu.com.cn/problem/P2762

本题很重要

最大权闭合子图

具体可参考论文《最小割模型在信息学竞赛中的应用》。

看似是费用流,其实是最小割问题。

由于做实验一定包含某些器材,所以从实验向对应器材连INF的边,实验为正权点,器材为负权点,则要找到一个子图,满足包含起点则一定包含终点,且点权和最大。

最终原图所有正权点的权和减去求得的最大流就是答案。

至于输出答案,可以利用最后一次增广后的残余网络,

与源点S连通的点就是最后的闭合子图中的点,可以从S沿不满流(因为满流的边相当于被“割”掉了,不会连接同属于S点集的点)的边dfs,也可以直接用求最大流时的vis或d数组来判断与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
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
typedef pair<int, int> pii;
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;

struct mxfl
{
int n = 0;
int m = 0;
int s, t;
struct Edge
{
int from, to, cap, flow;
};
vector<Edge>edges;
vector<int>G[maxn];
void init(int _n, int _s, int _t) {
n = _n;
s = _s;
t = _t;
edges.clear();
for (int i = 0; i < n; i++)G[i].clear();
}
void add_edge(int from, int to, int cap) {
edges.push_back(Edge{ from,to,cap,0 });
edges.push_back(Edge{ to,from,0,0 });
m = (int)edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool vis[maxn];
int d[maxn], cur[maxn];
bool bfs() {
memset(vis, 0, sizeof(vis));
queue<int>Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while (!Q.empty()) {
int x = Q.front(); Q.pop();
for (int i = 0; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x, int a) {
if (x == t || a == 0)return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0)break;
}
}
return flow;
}
int maxflow() {
int flow = 0;
while (bfs()) {
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
}MF;
int n, m;
int sum;
int main() {
scanf("%d%d", &n, &m);
int S = 0, T = n + m + 1;
MF.init(n + m + 2, S, T);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
sum += x;
MF.add_edge(S, i, x);
char tools[10000];
memset(tools, 0, sizeof tools);
cin.getline(tools, 10000);
int ulen = 0, tool;
while (sscanf(tools + ulen, "%d", &tool) == 1)//之前已经用scanf读完了赞助商同意支付该实验的费用
{//tool是该实验所需仪器的其中一个
MF.add_edge(i, tool + n, INF);
if (tool == 0)
ulen++;
else {
while (tool) {
tool /= 10;
ulen++;
}
}
ulen++;
}
}
for (int i = 1; i <= m; i++) {
int x;
scanf("%d", &x);
MF.add_edge(i + n, T, x);
}
int res = sum - MF.maxflow();
for (int i = 1; i <= n; i++)if (MF.vis[i])printf("%d ", i);
printf("\n");
for (int i = 1; i <= m; i++)if (MF.vis[i + n])printf("%d ", i);
printf("\n");
printf("%d\n", res);
return 0;
}

 

分配问题

https://www.luogu.com.cn/problem/P4014

最大权完备匹配

KM

最小的话把权值改成负的。

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>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 100 + 10;
const int INF = 0x3f3f3f3f;
int w[maxn][maxn];
int lx[maxn], ly[maxn];
int linker[maxn];
int slack[maxn];
int n;
bool visy[maxn];
int pre[maxn];
void bfs(int k) {
int x, y = 0, yy = 0, delta;
memset(pre, 0, sizeof(pre));
for (int i = 1; i <= n; i++) slack[i] = INF;
linker[y] = k;
while (1) {
x = linker[y]; delta = INF; visy[y] = true;
for (int i = 1; i <= n; i++) {
if (!visy[i]) {
if (slack[i] > lx[x] + ly[i] - w[x][i]) {
slack[i] = lx[x] + ly[i] - w[x][i];
pre[i] = y;
}
if (slack[i] < delta) delta = slack[i], yy = i;
}
}
for (int i = 0; i <= n; i++) {
if (visy[i]) lx[linker[i]] -= delta, ly[i] += delta;
else slack[i] -= delta;
}
y = yy;
if (linker[y] == -1) break;
}
while (y) linker[y] = linker[pre[y]], y = pre[y];
}

int KM() {
memset(lx, 0, sizeof(lx));
memset(ly, 0, sizeof(ly));
memset(linker, -1, sizeof(linker));
for (int i = 1; i <= n; i++) {
memset(visy, false, sizeof(visy));
bfs(i);
}
int res = 0;
for (int i = 1; i <= n; i++) {
if (linker[i] != -1) {
res += w[linker[i]][i];
}
}
return res;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &w[i][j]);
}
}
int ans1 = KM();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = -w[i][j];
}
}
cout << -KM() << endl;
cout << ans1 << endl;
return 0;
}

 

运输问题

https://www.luogu.com.cn/problem/P4015

费用流

因为题目说了“供需平衡”,相当于源汇流量相等,直接连边即可。

最大费用就把费用取负,跑最小费用。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 100 + 10;
const int INF = 0x3f3f3f3f;
struct E
{
int from, to, cp, v;
int rev;
E() {}
E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {}
};
struct MCMF
{
int n, m, s, t;
vector<E> edges;
vector<int> G[maxn];
bool inq[maxn]; //是否在队列
int d[maxn]; //Bellman_ford单源最短路径
int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号
int a[maxn]; //a[i]表示从s到i的最小残量
void init(int _n, int _s, int _t) {
n = _n; s = _s; t = _t;
for (int i = 0; i < n; i++) G[i].clear();
edges.clear(); m = 0;
}

void addedge(int from, int to, int cap, int cost) {
edges.push_back(E(from, to, cap, cost, 0));
edges.push_back(E(to, from, 0, -cost, 1));
G[from].push_back(m++);
G[to].push_back(m++);
}

bool BellmanFord(int &flow, int &cost) {
for (int i = 0; i < n; i++) d[i] = INF;
memset(inq, 0, sizeof inq);
d[s] = 0, a[s] = INF, inq[s] = true;
queue<int> Q; Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for (int& idx : G[u]) {
E &e = edges[idx];
if (e.cp && d[e.to] > d[u] + e.v) {
d[e.to] = d[u] + e.v;
p[e.to] = idx;
a[e.to] = min(a[u], e.cp);
if (!inq[e.to]) {
Q.push(e.to);
inq[e.to] = true;
}
}
}
}
if (d[t] == INF) return false;
//if (flow + a[t] > K)a[t] = K - flow;//固定流量
flow += a[t];
cost += a[t] * d[t];
int u = t;
while (u != s) {
edges[p[u]].cp -= a[t];
edges[p[u] ^ 1].cp += a[t];
u = edges[p[u]].from;
}
//if (flow == K)return false;//固定流量
return true;
}

pii go() {
int flow = 0, cost = 0;
while (BellmanFord(flow, cost));
return pii(flow, cost);
}
} MM;
int n, m;
int a[maxn], b[maxn], co[maxn][maxn];
void solve(int x) {
int S = 0, T = n + m + 1;
MM.init(n + m + 2, S, T);
for (int i = 1; i <= n; i++) {
int x = a[i];
MM.addedge(S, i, x, 0);
}
for (int i = 1; i <= m; i++) {
int x = b[i];
MM.addedge(i + n, T, x, 0);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int w = co[i][j];
MM.addedge(i, j + n, INF, w*x);
}
}
printf("%d\n", x*MM.go().second);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
for (int i = 1; i <= m; i++)scanf("%d", &b[i]);
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)
scanf("%d", &co[i][j]);
solve(1);
solve(-1);
return 0;
}

 

负载平衡问题

https://www.luogu.com.cn/problem/P4016

数论

费用流

从源点连到仓库容量 a[i]a[i],表示仓库自身能提供的最大库存(不包含其他仓库转过来的),每个仓库连到左右仓库,容量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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 100 + 10;
const int INF = 0x3f3f3f3f;
struct E
{
int from, to, cp, v;
int rev;
E() {}
E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {}
};
struct MCMF
{
int n, m, s, t;
vector<E> edges;
vector<int> G[maxn];
bool inq[maxn]; //是否在队列
int d[maxn]; //Bellman_ford单源最短路径
int p[maxn]; //p[i]表从s到i的最小费用路径上的最后一条弧编号
int a[maxn]; //a[i]表示从s到i的最小残量
void init(int _n, int _s, int _t) {
n = _n; s = _s; t = _t;
for (int i = 0; i < n; i++) G[i].clear();
edges.clear(); m = 0;
}

void addedge(int from, int to, int cap, int cost) {
edges.push_back(E(from, to, cap, cost, 0));
edges.push_back(E(to, from, 0, -cost, 1));
G[from].push_back(m++);
G[to].push_back(m++);
}

bool BellmanFord(int &flow, int &cost) {
for (int i = 0; i < n; i++) d[i] = INF;
memset(inq, 0, sizeof inq);
d[s] = 0, a[s] = INF, inq[s] = true;
queue<int> Q; Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for (int& idx : G[u]) {
E &e = edges[idx];
if (e.cp && d[e.to] > d[u] + e.v) {
d[e.to] = d[u] + e.v;
p[e.to] = idx;
a[e.to] = min(a[u], e.cp);
if (!inq[e.to]) {
Q.push(e.to);
inq[e.to] = true;
}
}
}
}
if (d[t] == INF) return false;
//if (flow + a[t] > K)a[t] = K - flow;//固定流量
flow += a[t];
cost += a[t] * d[t];
int u = t;
while (u != s) {
edges[p[u]].cp -= a[t];
edges[p[u] ^ 1].cp += a[t];
u = edges[p[u]].from;
}
//if (flow == K)return false;//固定流量
return true;
}

pii go() {
int flow = 0, cost = 0;
while (BellmanFord(flow, cost));
return pii(flow, cost);
}
} MM;
int n;
int ave, a[maxn];
int main() {
scanf("%d", &n);
int S = 0, T = n + 1;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
ave += a[i];
}
ave /= n;
MM.init(n + 2, S, T);
for (int i = 1; i <= n; i++) {
MM.addedge(S, i, a[i], 0);
MM.addedge(i, i%n + 1, INF, 1);
MM.addedge(i, (i - 2 + n) % n + 1, INF, 1);
MM.addedge(i, T, ave, 0);
}
cout << MM.go().second << endl;
return 0;
}

 

然而,本题还有数论做法。

建议参考[[HAOI2008]糖果传递]](https://www.luogu.com.cn/problem/P2512)。

一个环形,每次只能在相邻之间传递,要求使每个人拥有相等数量糖果的最小传递数。

a1a_1 为每个人原有的糖果数,aveave 为平均值,也是最终每个人都有的糖果数。

每个人只会把糖果传给相邻人或从相邻人处得到。由于是个环,所以假设每个人都传给左边。

则,最终

{a1x1+x2=avea2x2+x3=avean1xn1+xn=aveanxn+x1=ave\begin{cases} a_1-x_1+x_2=ave\\ a_2-x_2+x_3=ave\\ \cdots\\ a_{n-1}-x_{n-1}+x_n=ave\\ a_n-x_n+x_1=ave \end{cases}

 

移项得到

{x2=x1(a1ave)x3=x2(a2ave)=x1(a2ave)(a1ave)xn=xn1(an1ave)=x1(an1ave)(an2ave)(a1ave)x1=x1=x1(anave)(an1ave)(a2ave)(a1ave)最后一步是由于(a1+a2++an)=nave\begin{cases} x_2=x_1-(a_1-ave)\\ x_3=x_2-(a_2-ave)=x_1-(a_2-ave)-(a_1-ave)\\ \cdots\\ x_n=x_{n-1}-(a_{n-1}-ave)=x_1-(a_{n-1}-ave)-(a_{n-2}-ave)-\cdots -(a_1-ave)\\ x_1=x_1=x_1-(a_n-ave)-(a_{n-1}-ave)-\cdots -(a_2-ave)-(a_1-ave)\\ 最后一步是由于(a_1+a_2+\cdots +a_n)=n\cdot ave \end{cases}

 

Ci=aiaveC_i=a_i-ave ,则

{x2=x1i=11Cix3=x1i=12Cixn=x1i=1n1Cix1=x1i=1nCi\begin{cases} x_2=x_1-\sum_{i=1}^1 C_i\\ x_3=x_1-\sum_{i=1}^2 C_i\\ \cdots\\ x_n=x_1-\sum_{i=1}^{n-1} C_i\\ x_1=x_1-\sum_{i=1}^n C_i \end{cases}

 

再设 sumi=i=1iCisum_i=\sum_{i=1}^i C_i,则

{x2=x1sum1x3=x1sum2xn=x1sumn1x1=x1sumn\begin{cases} x_2=x_1-sum_1\\ x_3=x_1-sum_2\\ \cdots\\ x_n=x_1-sum_{n-1}\\ x_1=x_1-sum_n\\ \end{cases}

 

要求 ans=minimize(x1+x2+xn1+xn)ans=minimize(|x_1|+|x_2|+\cdots |x_{n-1}|+|x_n|),则

ans=minimize(x1sum1+x1sum2++x1sumn1+x1sumn)ans=minimize(|x_1-sum_1|+|x_1-sum_2|+\cdots +|x_1-sum_{n-1}|+|x_1-sum_n|)

 

其中只有 x1x_1 一个变量,其他都是常量,则本题变为在一维坐标轴上找到一个点,到所有已知点的距离的绝对值之和最小。

这就是中位数。

x1x_1sum1,sum2,,sumn1,sumnsum_1,sum_2,\cdots ,sum_{n-1},sum_n 的中位数。

求出 x1x_1 后代入得到 ansans

贴上本题代码,在“糖果传递”也是一样代码。

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>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int n;
ll ave;
ll a[maxn], C[maxn];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
ave += a[i];
}
ave /= n;
for (int i = 1; i <= n; i++) {
C[i] = C[i - 1] + ave - a[i];
}
sort(C + 1, C + n + 1);
ll x = C[(n + 1) / 2];
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans += abs(x - C[i]);
}
printf("%lld\n", ans);
return 0;
}

 

深海机器人问题

https://www.luogu.com.cn/problem/P4012

看了半天,才发现给的是边权。

那么更简单,不用拆点,直接连边后费用流。

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>
#define pu(x,y) (x-1)*Q+y
using namespace std;
const int INF=1e8,MAX=400001,Max=1001,s=0,t=1000;
struct p{
int x,y,dis,cn;
}c[MAX];
int a,b,P,Q,num,tot1;
int h[Max],d[Max],last[Max],pre[Max];
bool use[Max];
void add(int x,int y,int dis,int cn)
{
c[num].x=h[y];c[num].y=x;c[num].dis=0,c[num].cn=-cn;h[y]=num++;
c[num].x=h[x];c[num].y=y;c[num].dis=dis,c[num].cn=cn;h[x]=num++;
}
void EK()
{
while(1)
{
queue<int> qu;
qu.push(0);
memset(d,127,sizeof(d));
d[0]=0;
while(!qu.empty())
{
int tt=qu.front();
qu.pop();
use[tt]=0;
for(int i=h[tt];i;i=c[i].x)
if(d[c[i].y]>d[tt]+c[i].cn&&c[i].dis)
{
d[c[i].y]=d[tt]+c[i].cn;
pre[c[i].y]=i;
if(!use[c[i].y])
{
use[c[i].y]=1;
qu.push(c[i].y);
}
}
}
if(d[t]>1e7) return;
int hh=t,sum=1e9;
while(pre[hh])
{
int l=pre[hh];
sum=min(sum,c[l].dis);
hh=c[l^1].y;
}
hh=t;
while(pre[hh])
{
int l=pre[hh];
c[l].dis-=sum;
c[l^1].dis+=sum;
tot1+=sum*c[l].cn;
hh=c[l^1].y;
}
}
}
int main()
{
scanf("%d%d%d%d",&a,&b,&P,&Q);
P++,Q++;
for(int i=1;i<=P;i++)
for(int j=1;j<Q;j++)
{
int x,hh=pu(i,j),tt=hh+1;
scanf("%d",&x);
add(hh,tt,1,-x);
add(hh,tt,INF,0);
}
for(int j=1;j<=Q;j++)
for(int i=1;i<P;i++)
{
int x,hh=pu(i,j),tt=hh+Q;
scanf("%d",&x);
add(hh,tt,1,-x);
add(hh,tt,INF,0);
}
for(int i=1;i<=a;i++)
{
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
x++,y++;
add(s,pu(x,y),k,0);
}
for(int i=1;i<=b;i++)
{
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
x++,y++;
add(pu(x,y),t,k,0);
}
EK();
printf("%d",-tot1);
return 0;
}

 

最小路径覆盖问题

https://www.luogu.com.cn/problem/P2764

最小路径覆盖模板题

拆点后连边

同一个点拆成的两个点之间不要连边。

有向图最小路径覆盖=原顶点数-拆点后最大匹配

相连的点在一条路径上,可以理解为匹配使路径数减少

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;

const int MAXN = 150 << 2;
const int MAXM = 6000 + 100;
const int INF = 1 << 30;

struct Edge {
int bg, ed, nxt, flow;
Edge(int bg = 0, int ed = 0, int nxt = 0, int flow = 0) :
bg(bg), ed(ed), nxt(nxt), flow(flow) {};
};

struct Map {
Edge edge[MAXM << 1];
int head[MAXN], count = 1;
inline void insert(int bg, int ed, int flow) {
edge[++count] = Edge(bg, ed, head[bg], flow);
head[bg] = count;
edge[++count] = Edge(ed, bg, head[ed], 0);
head[ed] = count;
}
}A;

int depth[MAXN], gap[MAXN], cur[MAXN];
int n, m;
bool vis[MAXN];

void bfs(int s, int t) {
memset(depth, 0, sizeof(depth));
memset(gap, 0, sizeof(depth));
queue<int> que;
que.push(t);
depth[t] = 1;
gap[1] = 1;
while (!que.empty()) {
int now = que.front();
que.pop();
for (int i = A.head[now]; i; i = A.edge[i].nxt) {
int v = A.edge[i].ed;
if (depth[v]) continue;
que.push(v);
depth[v] = depth[now] + 1;
++gap[depth[v]];
}
}
}

int dfs(int now, int flow, int s, int t) {
if (now == t) return flow;
int used = 0;
for (int i = cur[now]; i; i = A.edge[i].nxt) {
cur[now] = i;
int v = A.edge[i].ed;
if (A.edge[i].flow && depth[v] + 1 == depth[now]) {
int change = dfs(v, min(flow - used, A.edge[i].flow), s, t);
A.edge[i].flow -= change;
A.edge[i ^ 1].flow += change;
used += change;
}
if (used == flow) return used;
}
--gap[depth[now]];
if (!gap[depth[now]]) depth[s] = (n << 1) + 1;
++depth[now];
++gap[depth[now]];
return used;
}

int ISAP(int s, int t) {
bfs(s, t);
int ans = 0;
while (depth[s] <= (n << 1)) {
memcpy(cur, A.head, sizeof(A.head));
ans += dfs(s, INF, s, t);
}
return ans;
}

void print(int now, int s, int t) {
printf("%d ", now);
for (int i = A.head[now]; i; i = A.edge[i].nxt) {
if (A.edge[i].flow || A.edge[i].ed == s || A.edge[i].ed == now + n) continue;//这里要注意的是不要把边连回自己
print(A.edge[i].ed - n, s, t);//下一个点应从xi出发搜索,所以要减n
return;
}
}

int main() {
memset(vis, false, sizeof(vis));
int x, y, s, t, ans;
scanf("%d%d", &n, &m);
s = 2 * n + 5, t = s + 1, ans = n;
for (int i = 1; i <= n; ++i) {
A.insert(s, i, 1);
A.insert(i + n, t, 1);
}
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &x, &y);
A.insert(x, y + n, 1);
}
ans -= ISAP(s, t);
for (int i = 1; i <= n; ++i) {
bool flag = false;
for (int j = A.head[i + n]; j; j = A.edge[j].nxt) //查找yi
if (A.edge[j].flow && A.edge[j].ed != i && A.edge[j].ed != t) {
flag = true;
break;
}
if (!flag) {
print(i, s, t);//递归输出
printf("\n");
}
}
printf("%d\n", ans);
return 0;
}

 

最长k可重区间集问题

https://www.luogu.com.cn/problem/P3358

费用流,经典模型

对每一个区间,从区间起点向终点连一条容量为 11,费用为 len[i]-len[i] 的边。

对所有点 ii,连接 ii 与其相邻点 i+1i+1 ,容量为 kk,费用为 00.

建一个源点S,汇点T,从S向最左边的点连边,容量为 kk,费用为 00。从最右边的点向T连边,容量为 kk,费用为 00

这样可以限制每一段小区间的最大流量为 kk ,且若有一个大区间跨过几个小区间,必定有1的流量流过大区间,且每一个被跨过的小区间都受到其影响,流量都不得不减1.有点类似差分。

最后,由于区间端点可能很大,所以要离散化。

离散化的时候一定要erase!!不然谁知道lower_bound出来什么鬼东西

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int maxn = 1000 + 10;
const int INF = 0x3f3f3f3f;
struct E {
int from, to;
ll cp;
ll v;
int rev;
E() {}
E(int f, int t, ll cp, ll v, int rev) : from(f), to(t), cp(cp), v(v), rev(rev) {}
};
struct MCMF {
int n, m, s, t;
vector<E> edges;
vector<int> G[maxn];
bool inq[maxn]; //是否在队列
ll d[maxn]; // Bellman_ford单源最短路径
int p[maxn]; // p[i]表从s到i的最小费用路径上的最后一条弧编号
ll a[maxn]; // a[i]表示从s到i的最小残量
void init(int _n, int _s, int _t) {
n = _n;
s = _s;
t = _t;
for (int i = 0; i < n; i++) G[i].clear();
edges.clear();
m = 0;
}

void addedge(int from, int to, ll cap, ll cost) {
edges.push_back(E(from, to, cap, cost, 0));
edges.push_back(E(to, from, 0, -cost, 1));
G[from].push_back(m++);
G[to].push_back(m++);
}

bool BellmanFord(ll &flow, ll &cost) {
for (int i = 0; i < n; i++) d[i] = INF;
memset(inq, 0, sizeof inq);
d[s] = 0, a[s] = INF, inq[s] = true;
queue<int> Q;
Q.push(s);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
inq[u] = false;
for (int &idx : G[u]) {
E &e = edges[idx];
if (e.cp && d[e.to] > d[u] + e.v) {
d[e.to] = d[u] + e.v;
p[e.to] = idx;
a[e.to] = min(a[u], e.cp);
if (!inq[e.to]) {
Q.push(e.to);
inq[e.to] = true;
}
}
}
}
if (d[t] == INF)
return false;
// if (flow + a[t] > K)a[t] = K - flow;//固定流量
flow += a[t];
cost += a[t] * d[t];
int u = t;
while (u != s) {
edges[p[u]].cp -= a[t];
edges[p[u] ^ 1].cp += a[t];
u = edges[p[u]].from;
}
// if (flow == K)return false;//固定流量
return true;
}

pii go() {
ll flow = 0;
ll cost = 0;
while (BellmanFord(flow, cost))
;
return pii(flow, cost);
}
} MM;
int n, k;
vector<ll> vc;
ll L[maxn], R[maxn];
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
scanf("%lld%lld", &L[i], &R[i]);
if (L[i] > R[i])
swap(L[i], R[i]);
vc.push_back(L[i]);
vc.push_back(R[i]);
}
sort(vc.begin(), vc.end());
vc.erase(unique(vc.begin(),vc.end()),vc.end());
int N = vc.size();
int S = N, T = N + 1;
MM.init(N + 2, S, T);
for (int i = 0; i < n; i++) {
L[i] = lower_bound(vc.begin(), vc.end(), L[i]) - vc.begin();
R[i] = lower_bound(vc.begin(), vc.end(), R[i]) - vc.begin();

MM.addedge(L[i], R[i], 1ll, -(vc[R[i]] - vc[L[i]]));
}
MM.addedge(S, 0, k, 0);
for (int i = 0; i < N - 1; i++) {
MM.addedge(i, i + 1, k, 0);
}
MM.addedge(N - 1, T, k, 0);
cout << -MM.go().second << endl;
return 0;
}

 

最长k可重线段集问题

https://www.luogu.com.cn/problem/P3357

与上一题类似,建图方式相同,不同点在于费用的设定,费用变为二维的欧几里得距离。

还有一点要注意,如果输入线段的两个端点x坐标相同,映射到x坐标上只有一个点,相当于产生了自环,而由于费用流设置费用时是取得相反数,所以就产生了负圈。

看了题解,把坐标轴拉伸两倍,使得原先每一个格现在有两格空间,则若两端点相同,就把R[i]++,否则L[i]++。

实际上这就像是拆点,把自环变为内部连接,从出点向其它入点连边,从入点接受其他点连边。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int maxn = 1000 + 10;
const ll INF = 1e18;
const int inf = 0x3f3f3f3f;
struct E {
int from, to;
ll cp;
ll v;
int rev;
E() {}
E(int f, int t, ll cp, ll v, int rev) : from(f), to(t), cp(cp), v(v), rev(rev) {}
};
struct MCMF {
int n, m, s, t;
vector<E> edges;
vector<int> G[maxn];
bool inq[maxn]; //是否在队列
ll d[maxn]; // Bellman_ford单源最短路径
int p[maxn]; // p[i]表从s到i的最小费用路径上的最后一条弧编号
ll a[maxn]; // a[i]表示从s到i的最小残量
void init(int _n, int _s, int _t) {
n = _n;
s = _s;
t = _t;
for (int i = 0; i < n; i++) G[i].clear();
edges.clear();
m = 0;
}

void addedge(int from, int to, ll cap, ll cost) {
edges.push_back(E(from, to, cap, cost, 0));
edges.push_back(E(to, from, 0, -cost, 1));
G[from].push_back(m++);
G[to].push_back(m++);
}

bool BellmanFord(ll &flow, ll &cost) {
for (int i = 0; i < n; i++) d[i] = INF;
memset(inq, 0, sizeof inq);
d[s] = 0, a[s] = INF, inq[s] = true;
queue<int> Q;
Q.push(s);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
inq[u] = false;
for (int &idx : G[u]) {
E &e = edges[idx];
if (e.cp && d[e.to] > d[u] + e.v) {
d[e.to] = d[u] + e.v;
p[e.to] = idx;
a[e.to] = min(a[u], e.cp);
if (!inq[e.to]) {
Q.push(e.to);
inq[e.to] = true;
}
}
}
}
if (d[t] == INF)
return false;
// if (flow + a[t] > K)a[t] = K - flow;//固定流量
flow += a[t];
cost += a[t] * d[t];
int u = t;
while (u != s) {
edges[p[u]].cp -= a[t];
edges[p[u] ^ 1].cp += a[t];
u = edges[p[u]].from;
}
// if (flow == K)return false;//固定流量
return true;
}

pii go() {
ll flow = 0;
ll cost = 0;
while (BellmanFord(flow, cost));
return pii(flow, cost);
}
} MM;
int n, k;
vector<ll>vc;
ll dis(ll x1, ll y1, ll x2, ll y2) {
return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}
ll w[maxn];
int L[maxn], R[maxn];
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) {
ll x1, y1, x2, y2;
scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
w[i] = dis(x1, y1, x2, y2);
if (x1 > x2)swap(x1, x2);
x1 <<= 1, x2 <<= 1;
L[i] = x1, R[i] = x2;
if (x1 == x2) R[i] |= 1;
else L[i] |= 1;
vc.push_back(L[i]);
vc.push_back(R[i]);
}
sort(vc.begin(), vc.end());
vc.erase(unique(vc.begin(), vc.end()), vc.end());
int N = vc.size();
int S = N, T = N + 1;
MM.init(N + 2, S, T);
for (int i = 0; i < n; i++) {
L[i] = lower_bound(vc.begin(), vc.end(), L[i]) - vc.begin();
R[i] = lower_bound(vc.begin(), vc.end(), R[i]) - vc.begin();
MM.addedge(L[i], R[i], 1, -w[i]);
}
for (int i = 0; i < N - 1; i++) {
MM.addedge(i, i + 1, k, 0);
}
MM.addedge(S, 0, k, 0);
MM.addedge(N - 1, T, k, 0);
cout << -MM.go().second << endl;
return 0;
}

 

最长不下降子序列问题

https://www.luogu.com.cn/problem/P2766

dp+最大流

刚开始以为最小路径覆盖可以,结果发现路径数最少不代表每条路最长,gg。

先dp出s,即最长长度。

本题是一个点权问题,因此默认要拆点。

再建立一个分层图,对于每个点,只与它后面dp值=它的dp值+1且值比它大的点连边。表示可以组成一条路径。这样就保证了答案的完整性。

再从S向dp值=1的点连边,从dp值=s的点向T连边,所有边容量都为1.

而第三问就是首位两个点点权为INF,则添加S到第一个点,容量为INF的边,首尾两点内部容量为INF的边。注意,由于末尾点的dp值不一定是s,所以不能直接从末尾点向T连边。

还有一点比较坑,要特判n=1的情况,第三问答案为1,但按照题目要求,答案不应该是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
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
struct mxfl {
int n = 0;
int m = 0;
int s, t;
struct Edge {
int from, to, cap, flow;
};
vector<Edge> edges;
vector<int> G[maxn];
void init(int _n, int _s, int _t) {
n = _n;
s = _s;
t = _t;
edges.clear();
for (int i = 0; i < n; i++) G[i].clear();
}
void add_edge(int from, int to, int cap) {
edges.push_back(Edge{ from, to, cap, 0 });
edges.push_back(Edge{ to, from, 0, 0 });
m = (int)edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool vis[maxn];
int d[maxn], cur[maxn];
bool bfs() {
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while (!Q.empty()) {
int x = Q.front();
Q.pop();
for (int i = 0; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x, int a) {
if (x == t || a == 0)
return a;
int flow = 0, f;
for (int& i = cur[x]; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0)
break;
}
}
return flow;
}
int maxflow() {
int flow = 0;
while (bfs()) {
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
} MF;
int n, a[maxn];
int dp[maxn];
int s;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
if (n == 1) {
printf("1\n1\n1\n");
return 0;
}
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (a[j] <= a[i])
dp[i] = max(dp[i], dp[j] + 1);
}
}
for (int i = 0; i < n; i++) s = max(s, dp[i]);
cout << s << endl;
int N = 2 * n + 2;
int S = N - 2, T = N - 1;
MF.init(N, S, T);
for (int i = 0; i < n; i++) {
MF.add_edge(i << 1, i << 1 | 1, 1);
if (dp[i] == 1)
MF.add_edge(S, i << 1, 1);
if (dp[i] == s)
MF.add_edge(i << 1 | 1, T, 1);
for (int j = i + 1; j < n; j++) {
if (a[i] <= a[j] && dp[j] == dp[i] + 1)
MF.add_edge(i << 1 | 1, j << 1, 1);
}
}
int ans = MF.maxflow();
cout << ans << endl;
MF.add_edge(S, 0, INF);
MF.add_edge(0, 1, INF);
if (dp[n - 1] == s)
MF.add_edge((n - 1) << 1 | 1, T, INF);
MF.add_edge((n - 1) << 1, (n - 1) << 1 | 1, INF);
cout << (ans + MF.maxflow()) << endl;
return 0;
}

 

软件补丁问题

https://www.luogu.com.cn/problem/P2761

这题在洛谷上已经被踢出24题了,是因为太简单了吗。。

状压dp+Dijkstara

根据错误的位置dp。对于每个补丁,用位运算check是否满足条件,再位运算处理出结果。由于只有正权边,Dijkstara即可。

数组开大点。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 1e7 + 10;
const int INF = 0x3f3f3f3f;

int n, m;
int w[maxn];
char s[maxn];
int ck1[maxn], ck2[maxn];
int b1[maxn], b2[maxn];
int vis[maxn], d[maxn];
int Dij(int s) {
priority_queue<pii, vector<pii>, greater<pii> >que;
memset(d, 0x3f, sizeof(d));
d[s] = 0;
que.push(pii(0,s));
while (!que.empty()) {
pii tp = que.top(); que.pop();
int u = tp.second, dis = tp.first;
if (u == 0)return dis;
if (vis[u])continue;
vis[u] = 1;
for (int i = 0; i < m; i++) {
if (((ck1[i] ^ u)&ck2[i]) == 0) {
int nu = (u&b1[i]) | b2[i];
if ((!vis[nu]) && d[nu] > dis + w[i]) {
d[nu] = dis + w[i];
que.push(pii(d[nu], nu));
}
}
}
}
return 0;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d", &w[i]);
scanf("%s", s);
for (int j = 0; j < n; j++) {
if (s[j] == '+')ck1[i] |= (1 << j);
if (s[j] != '0')ck2[i] |= (1 << j);
}
scanf("%s", s);
for (int j = 0; j < n; j++) {
if (s[j] == '+')b2[i] |= (1 << j);
if (s[j] != '-')b1[i] |= (1 << j);
}
}
int s = (1 << n) - 1;
cout << Dij(s) << endl;
return 0;
}

 

机器人路径规划问题

https://www.luogu.com.cn/problem/P2775

著名假题?

题意:给定一棵树,其中有一些节点有可移动的障碍物,给出起点s,终点t,机器人和障碍物可以沿边移动,每个节点最多容纳一个物体(机器人或障碍物),要求从起点到终点,且机器人与障碍物总共的移动次数最少,求移动次数。

看似是一个点权为1的网络流问题,由于范围为1000,也不能状压。

看到洛谷上唯一一篇题解有LCA+dfs,不是很懂。

而且似乎题目说了给一棵树,但数据里有环,所以成了道孤儿题。。

 

总结

终于把24 23题刷完了,总的做下来感觉并不是特别难。适合入门练习,指的是只会用板子,不会路径输出,不懂原理的入门。其中也有一些最大独立集,最小路径覆盖,二分图匹配等,对于思路的拓展很有帮助。最小割在这套题中尽管出现不多,但出现的地方也都挺经典的,值得一做。也有一些状压dp+最短路的题,算是我遇到的新题了。

 

其中有几道题看了题解才会,值得做一下:

  • 餐巾计划问题
  • 方格取数问题
  • 家园
  • 太空飞行计划问题
  • 负载平衡问题(数论部分)
  • 最长k可重线段集问题
  • 最长不下降子序列问题

 

还有一些题是某些类型的代表题目:

  • 魔术球问题(有向图最小路径覆盖)
  • 孤岛营救问题(状压dp)
  • 火星探险问题(拆点,路径输出)
  • 方格取数问题(最小割)
  • 骑士共存问题(最大独立集)
  • 家园(分层图经典模型)
  • 最长不下降子序列问题(分层图经典模型)
  • 太空飞行计划问题(最大权闭合子图)
  • 分配问题(最大权完备匹配)
  • 最长k可重线段集问题(建图,拆点)

负载平衡问题的数论部分也还是很有趣的。

 

《最小割模型在信息学竞赛中的应用》这篇论文中讲解了很多最小割模型的应用与拓展,非常值得看。清晰版已经存在Github。

这套题目说实话有很大部分过于入门,只是重复性地建图,拆点输出路径,对模型的理解并没有要求,所以也就只适合入门。做完这套题,我也算正式成为一名蒻鸡了。

《训练指南》这本书里的网络流部分习题难度大于这套题,可以作为下一步刷题。