线性规划与网络流24题 Part 1

太菜了,现在才做网络流$24$题QAQ

「网络流 24 题」搭配飞行员 - 1

很明显的求二分图最大匹配的模板题呀QAQ

  • 建立源点 $s$ 连向每一个正驾驶员,容量为 $1$。
  • 建立汇点 $t$ 所有的副驾驶员连向 $t$,容量为 $1$。
  • 正驾驶员 $a$ 和副驾驶员 $b$ 可以同机飞行,那么连一条容量为$1$的边$a \rightarrow b$。

然后跑最大流就是答案了

「网络流 24 题」太空飞行计划 - 2

不会做啊QAQ,太菜了
最大权闭合图问题,可以转化成最小割问题,进而用最大流解决。

闭合子图就是给定一个有向图,从中选择一些点组成一个点集$V$。对于$V$中任意一个点,其后续节点都仍然在$V$中。
通俗的来说是 : 闭合图的性质反映的是事件的必要条件,$A$发生,那么$A$的所有前提要发生。

这道题目里 “ 要想做实验,先做某个实验必须购买好实验所需的设备 “ 构成了事件的必要条件。

先说结论吧,最大权闭合子图的权值等于所有正权点之和减去最小割 / 最大流。

本题要求最大化总收益,设配置仪器花 $C$ 元,这些仪器能进行的实验的总收益为 $P$,不能进行的实验的总收益为 $P’$ ,所有实验的总收益为 $Sum$,则

由于 $S$ 是定值,我们将问题转化到了在合法的情况下,让 $W’ + C$尽量小,于是构图如下:

  • 将每个实验划分为 $A$ 集合,每个仪器划分为 $B$ 集合。
  • 建立超级源点 $s$ 向 $A$ 集合中的每一个点连一条容量为该实验收益的边并累加 $sum$,建立超级汇点 $t$,$B$ 集合中的每一个点向汇点 $t$ 连一条容量为该仪器花费的边。
  • 如果 $A$ 集合中的实验 $A_{i}$ 需要$B$集合中的仪器 $B_{j}$,那么连边 $A_{i} \rightarrow B_{j}$ 容量为 $\infty$。
  • 跑一遍最大流,$ans = sum - maxFlow(s, t)$。

我们发现我们需要最小化的$P’ + C$相当于当前图中的最小割 / 最大流。

现在再想一下上面的结论为什么成立,我们需要最小化割,相当于用最小的流量使得 $s$ 与 $t$ 不连通。
对于一个实验,我们定义选择还是不选择实验 $A_{i}$ 通过是否割 $s \rightarrow A_{i}$ 这条边来判定,如果不选择实验 $A_{i}$ 则割掉 $s \rightarrow A_{i}$ 这条边; 如果选择实验 $A_{i}$ 则不割这条边,那么现在为了使得 $s \rightarrow t$ 不连通,那么就割掉实验 $A_{i}$ 所需的仪器集合 $B_{i}$ 连向 $t$ 的边 (我们肯定不会选择割容量为$\infty$的边)。
那么这样每一个合法的割的值就为 $P’ + C$,也就是说我们要最小化 $P’ + C$ 的值。

输出方案有一些恶心,这里不想写了,可以看线性规划与网络流24题 - 2 太空飞行计划

「网络流 24 题」最小路径覆盖 - 3

我们需要求有向无环图 $G$ 的最小路径覆盖。

最小路径覆盖 = 原图顶点数 - 二分图最大匹配数

我们可以观察一条路径,起点的入度为 $0$,终点的出度为 $0$,中间节点的出入度都为 $1$。也就是说,每一个点最多只能有 $1$ 个后继,同时每一个点最多只能有 $1$ 个前驱。
假如我们选择了一条边 $(u,v)$,也就等价于把前驱 $u$ 和后继 $v$ 匹配上了。这样前驱 $u$ 和后继 $v$ 就不能和其他节点匹配。

  • 将每一个点拆分成 $2$ 个,分别表示它作为前驱节点和后继节点,将所有的前驱结点作为 $A$ 集合,所有后继结点作为 $B$ 集合。
  • 若原图中存在一条边$(u,v)$,则连接$A$集合的$u$和$B$集合的$v$。
  • 新建源汇 $s, t$,$s$ 向每个 $A_{i}$连边,$B_{i}$向 $t$ 连边。

如果一个点是路径起点的话,它在$B$集合的结点一定是没有匹配上的,做完二分图最大匹配之后,保证了$B$集合中未匹配的点最少,也就对应了最小路径覆盖数。

输出路径有一些麻烦,画一下图应该就会了吧QAQ

「网络流 24 题」魔术球 - 4

依然是一道很神奇的题目QAQ,听说贪心可以过,这里还是写网络流的做法吧

不好求有 $n$ 个柱子时可放的球数量,转换一下思路,我们求可放 $n$ 个球时的最小柱子数量,注意到同一个柱子上球的标号递增,所以可以转化为最小路径覆盖问题。

枚举答案 $A$,在图中建立节点 $1,2, \cdots ,A$。如果对于 $i<j$有 $i+j$为一个完全平方数,连接一条有向边 $(i,j)$。那么此时我们可以发现五门实际上是在求有向无环图的最小路径覆盖。

如果刚好满足最小路径覆盖数等于 $n$,那么 $A$ 是一个可行解,在所有可行解中找到最大的 $A$,即为最优解。
可以顺序枚举 $A$ 的值,当最小路径覆盖数刚好大于 $n$ 时终止,$A-1$就是最优解。

这道题目更适合枚举答案而不是二分答案,因为如果顺序枚举答案,每次只需要在残量网络上增加新的结点点和边,再增广一次即可。如果二分答案,就需要每次重新建图,大大增加了时间复杂度。

「网络流 24 题」圆桌聚餐 - 5

二分图多重匹配,为什么总是要输出方案呀QAQ

  • 把每一个代表单位当成$A$集合中的一个元素,每张餐桌当做$B$集合中的一个元素。
  • 建立超级源点$s$向$A$集合连一条容量为代表单位的人数; 建立超级汇点$t$,$B$集合中的每一个点向$t$连一条容量为餐桌最多容纳人数的边。保证每个单位参加人数不超过上限,每个餐桌容量不超过上限。
  • $A$集合中的每一个点向$B$集合中的每一个点连一条容量为$1$的点,保证了 “ 希望从同一个单位来的代表不在同一个餐桌就餐 “ 这个条件成立。若可以匹配多次则可以通过改变容量实现。
  • 跑一边最大流$ans = maxFlow(s, t)$,若$ans$小于每个单位人数之和则没有解,否则存在并输出答案。

二分图最大匹配中,每个点最多只能和一条匹配边相关联,然而,我们像以上这类问题,即二分图匹配中一个点可以和多条匹配边相关联,可以参考以上的建模方法。

「网络流 24 题」最长递增子序列 - 6

首先第一问可以用动态规划在 $\Theta(n^{2})$ 做的,令 $f[i]$ 表示以第 $i$ 为结尾的最长上升序列的长度,最后取 $max$ $f[i]$即可。

第二问,问最多可取同时出多少个长度为 $s$ 的递增子序列。每个数只能用一次,因此考虑拆点来限制每个点只能用一次这个条件

  • 把序列第$i$位拆成两个点$i_{a}$和$i_{b}$,从$i_{a}$到$i_{b}$连接一条容量为1的有向边
  • 建立超级源点$s$和超级汇点$t$,如果序列第 $i$ 位有 $f[i] = 1$,从 $s$ 到 $i_{a}$ 连接一条容量为 $1$ 的边
  • 如果有 $f[i]=1$,从 $i_{b}$ 到 $t$ 连接一条容量为1的有向边。
  • 如果$i < j$且$A[i] < A[j]$且$f[j] + 1 = f[i]$,从$i_{b}$到$j_{a}$连接一条容量为$1$边

简要分析一下,因为最上升子序列有明显的阶段性,$f[i]$的值为阶段,那么$f[i] = 1$相当与阶段的开始,而$f[i] = k$相当于阶段的结束,一束流量为$1$的流,只有经过 $k - 1$次转移,才能到从源点到达汇点,而每一束到达汇点的流,均对应一个 最长上升子序列,因此第二问的答案就是本图最大流。

会求第二问了,那么第三问也是一样的,只需要将边$(1_{a}, 1_{b})$,$(n_{a}, n_{b})$,$(s, 1_{a})$,$(n_{b}, t) (f[n] == k)$的容量修改为$\infty$,再求一次网络最大流,就是第三问结果。

调的有点久,因为位运算没有写括号进入了死循环 ???

「网络流 24 题」试题库 - 7

还是二分图多重匹配,题意描述的很玄妙呀QAQ
大概就是一张试卷需要含有$k$种属性的试题,每种属性的试题需要$k_{i}$道,现在题库中一共有$n$道试题,每道试题有$p$种属性,输出满足第$k$道试题的试卷选取情况。
建图方法同 “ 「网络流 24 题」圆桌聚餐 “ 。

  • 每一道试题当成$A$集合中的一个元素,试卷中所需的每种试题当做$B$集合中的一个元素。
  • 建立超级源点$s$向$A$集合连一条容量$1$; 建立超级汇点$t$,$B$集合中的每一个点向$t$连一条容量为每种试题需要数量。
  • $A$集合中的每一个点根据这道试题的类型向$B$集合中的代表此种类型的点连一条容量为$1$的点。
  • 跑一边最大流$ans = maxFlow(s, t)$,若$ans$小于每各种类的题所需数量之和则没有解,否则存在并输出答案。

「网络流 24 题」机器人路径规划问题 - 8

真 $\cdot$ 不会做,有没有大佬可以教我呀QAQ

代码

「网络流 24 题」搭配飞行员 - 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
//  Created by ZJYelizaveta on 2017年08月17日 星期四 09时27分02秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 100 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
int s, t;
int a[MAX_N], b[MAX_N];
int ans;

namespace dinic {
struct Edge {
int to, cap, rev;
Edge(int to, int cap, int rev) : to(to), cap(cap), rev(rev){}
};
vector<Edge> G[MAX_N];
int iter[MAX_N], level[MAX_N];

inline void addEdge(int from, int to, int cap) {
G[from].push_back(Edge(to, cap, G[to].size()));
G[to].push_back(Edge(from, 0, G[from].size() - 1));
}

bool bfs() {
queue<int> q;
memset(level, -1, sizeof level);
q.push(s), level[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)G[u].size(); i++) {
Edge &e = G[u][i];
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return ~level[t];
}

int dfs(int u, int flow) {
if(u == t) return flow;//

for (int &i = iter[u]; i < G[u].size(); i++) {
Edge &e = G[u][i];
if (e.cap && level[e.to] == level[u] + 1) {
int d = dfs(e.to, min(flow, e.cap));
if (d) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}

int maxFlow(int _s, int _t) {
s = _s, t = _t;
int flow = 0, d = 0;
while (bfs()) {
memset(iter, 0, sizeof iter);
while(d = dfs(s, INF), d) flow += d;
}
return flow;
}
}
using namespace dinic;

int main()
{
n = readIn(), m = readIn();
// printf("%d %d\n", n, m);
s = 0, t = n + 1;
for (int i = 1; i <= m; ++i) addEdge(s, i, 1);//
for (int i = m + 1; i <= n; ++i) addEdge(i, t, 1);//
int a, b;
while (scanf("%d%d", &a, &b) != EOF) {
if (a > b) swap(a, b);
addEdge(a, b, 1);
}
ans = maxFlow(s, t);
printf("%d\n", ans);
return 0;
}

「网络流 24 题」太空飞行计划 - 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
//  Created by ZJYelizaveta on Wednesday, September 20, 2017 PM02:14:25 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 100 + 3;
const int INF = 0x3f3f3f3f;
int m, n;
int s, t;
int c[MAX_N];
int ans, sum;

namespace Dinic {
struct Edge {
int to, cap, rev;
Edge (int to, int cap, int rev) : to(to), cap(cap), rev(rev){}
};
vector<Edge> G[MAX_N];
int iter[MAX_N], level[MAX_N];

inline void addEdge(int from, int to, int cap) {
G[from].push_back(Edge(to, cap, G[to].size()));
G[to].push_back(Edge(from, 0, G[from].size() - 1));
}

bool bfs() {
memset(level, -1, sizeof level);
queue<int> q;
q.push(s), level[s] = 0;

while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return ~level[t];
}

int dfs(int u, int flow) {
if (u == t) return flow;

for (int &i = iter[u]; i < G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap && level[e.to] == level[u] + 1) {
int d = dfs(e.to, min(e.cap, flow));
if (d) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}

int maxFlow(int _s, int _t) {
s = _s, t = _t;
int d = 0, flow = 0;
while (bfs()) {
memset(iter, 0, sizeof iter);
while (d = dfs(s, INF), d) flow += d;
}
return flow;
}
}
using namespace Dinic;

int vis[MAX_N << 1];
void dfs(int u) {
vis[u] = true;
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap && !vis[e.to]) dfs(e.to);
}
}

inline void printPath() {
memset(vis, 0, sizeof vis);
dfs(0);
for (int i = 1; i <= n; ++i) if (vis[i]) printf("%d ", i); printf("\n");
for (int i = 1; i <= m; ++i) if (vis[n + i]) printf("%d ", i); printf("\n");
}

int main()
{
n = readIn(), m = readIn();
// printf("%d %d\n", n, m);
s = 0, t = m + n + 1;
sum = 0;
for (int i = 1; i <= n; ++i) {
int num = readIn(); sum += num;
addEdge(s, i, num);
string s; int a;
getline(cin, s);
stringstream ss(s);
while (ss >> a) addEdge(i, a + n, INF);
}
for (int i = 1; i <= m; ++i) {
int x = readIn();
addEdge(i + n, t, x);
}
// printf("%d\n", sum);
// printf("%d\n", maxFlow(s, t));
ans = sum - maxFlow(s, t);
printPath();
printf("%d\n", ans);
return 0;
}

「网络流 24 题」最小路径覆盖 - 3

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
//  Created by ZJYelizaveta on 2017年08月17日 星期四 10时02分56秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 300 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
int s, t;
int ans;

namespace Dinic {
struct Edge {
int to, cap, rev;
Edge(int to, int cap, int rev) : to(to), cap(cap), rev(rev){}
};
vector<Edge> G[MAX_N << 1];
int iter[MAX_N << 1], level[MAX_N << 1];

inline void addEdge(int from, int to, int cap) {
G[from].push_back(Edge(to, cap, G[to].size()));
G[to].push_back(Edge(from, 0, G[from].size() - 1));
}

bool bfs() {
memset(level, -1, sizeof level);
queue<int> q;
q.push(s), level[s] = 0;

while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return ~level[t];
}

int dfs(int u, int flow) {
if (u == t) return flow;

for (int &i = iter[u]; i < G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap && level[e.to] == level[u] + 1) {
int d = dfs(e.to, min(e.cap, flow));//
if (d) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}

int maxFlow(int _s, int _t) {
s = _s, t = _t;
int flow = 0, d = 0;
while (bfs()) {
memset(iter, 0, sizeof iter);
while (d = dfs(s, INF), d) flow += d;
}
return flow;
}
}
using namespace Dinic;

int vis[MAX_N << 1], fa[MAX_N << 1], next[MAX_N << 1];
void dfs(int u) {
vis[u] = true;
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.to > n && e.to <= 2 * n && e.cap <= 0 && !vis[e.to]) {
next[u] = (e.to - n); fa[e.to - n] = fa[u];
dfs(e.to - n);
}
}
}

inline void printPath() {
memset(vis, 0, sizeof vis);
memset(next, 0, sizeof next);
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 1; i <= n; ++i) if (!vis[i]) dfs(i);
// for (int i = 1; i <= n; ++i) printf("%d %d\n", fa[i], i);
for (int i = 1; i <= n; ++i) if (fa[i] == i) {
for (int j = i; j; j = next[j]) printf("%d ", j);
printf("\n");
}

}

int main()
{
n = readIn(), m = readIn();
// printf("%d %d\n", n, m);
s = 0, t = 2 * n + 1;
for (int i = 1; i <= n; ++i) addEdge(s, i, 1);
for (int i = 1; i <= n; ++i) addEdge(i + n, t, 1);

for (int i = 1; i <= m; ++i) {
int u = readIn(), v = readIn();
addEdge(u, v + n, 1);
}
ans = n - maxFlow(s, t);
printPath();
printf("%d\n", ans);
return 0;
}

「网络流 24 题」魔术球 - 4

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
//  Created by ZJYelizaveta on 2017年08月19日 星期六 18时59分06秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 100000 + 3;
const int MAX_M = 1000000 + 3;
const int INF = 0x3f3f3f3f;

namespace Dinic {
struct Edge {
int to, cap, rev;
Edge (int to, int cap, int rev) : to(to), cap(cap), rev(rev){}
};
vector<Edge> G[MAX_N << 1];
int iter[MAX_N << 1], level[MAX_N];

inline void addEdge(int from, int to, int cap) {
G[from].push_back(Edge(to, cap, G[to].size()));
G[to].push_back(Edge(from, 0, G[from].size() - 1));
}

bool bfs(int s, int t) {
memset(level, -1, sizeof level);
queue<int> q;
q.push(s), level[s] = 0;

while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return ~level[t];
}

int dfs(int u, int t, int flow) {
if (u == t) return flow;

for (int &i = iter[u]; i < G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap && level[e.to] == level[u] + 1) {
int d = dfs(e.to, t, min(e.cap, flow));
if (d) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}

int maxFlow(int _s, int _t) {
int s = _s, t = _t;
int d = 0, flow = 0;
while (bfs(s, t)) {
memset(iter, 0, sizeof iter);
while (d = dfs(s, t, INF), d) flow += d;
}
return flow;
}
}
using namespace Dinic;

int vis[MAX_N], next[MAX_N];
inline void printPath(int n) {
memset(vis, 0, sizeof vis);
memset(next, 0, sizeof next);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < (int)G[i].size(); ++j) {
Edge &e = G[i][j];
if (e.to && e.cap <= 0) next[i] = e.to - 5000;//
}
}
for (int i = 1; i <= n; ++i) {
if (vis[i]) continue;
int x = i;
while (x) {
printf("%d ", x); x = next[x]; vis[x] = 1;
}
printf("\n");
}
}

set<int> S;
int main()
{
for (int i = 1; i <= 100; ++i) S.insert(i * i);
int n = readIn();
int st = 0, ed = 100000, m = 5000, ans = 0, cnt = 0;
for (int i = 1; ; ++i) {
addEdge(st, i, 1); addEdge(i + m, ed, 1);
for (int j = 1; j < i; ++j) if (S.count(i + j)) addEdge(j, i + m, 1);
ans += maxFlow(st, ed);
if (i - ans > n) {
printf("%d\n", i - 1);
cnt = i - 1;
break;
}
}
// printf("%d\n", cnt);
printPath(cnt);
return 0;
}

「网络流 24 题」圆桌聚餐 - 5

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
//  Created by ZJYelizaveta on 2017年08月17日 星期四 21时08分55秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 270 + 3;
const int MAX_M = 150 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
int s, t;
int ans, sum;

namespace Dinic {
struct Edge {
int to, cap, rev;
Edge(int to, int cap, int rev) : to(to), cap(cap), rev(rev){}
};
vector<Edge> G[MAX_N << 1];
int iter[MAX_N << 1], level[MAX_N << 1];

inline void addEdge(int from, int to, int cap) {
G[from].push_back(Edge(to, cap, G[to].size()));
G[to].push_back(Edge(from, 0, G[from].size() - 1));
}

bool bfs() {
memset(level, -1, sizeof level);
queue<int> q;
q.push(s), level[s] = 1;

while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return ~level[t];
}

int dfs(int u, int flow) {
if (u == t) return flow;

for (int &i = iter[u]; i < G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap && level[e.to] == level[u] + 1) {
int d = dfs(e.to, min(e.cap, flow));
if (d) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}

int maxFlow(int _s, int _t) {
s = _s, t = _t;
int flow = 0, d = 0;
while (bfs()) {
memset(iter, 0, sizeof iter);
while (d = dfs(s, INF), d) flow += d;
}
return flow;
}
}
using namespace Dinic;

inline void printPath() {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < (int)G[i].size(); ++j) {
Edge &e = G[i][j];
if (e.to > n && e.to <= n + m && !e.cap) printf("%d ", e.to - n);
}
printf("\n");
}
}

int main()
{
n = readIn(), m = readIn();
s = 0, t = n + m + 1;
sum = 0;
for (int i = 1; i <= n; ++i) {
int num = readIn(); sum += num;
addEdge(s, i, num);
}
for (int i = 1; i <= m; ++i) {
int num = readIn();
addEdge(i + n, t, num);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
addEdge(i, j + n, 1);
}
}
ans = maxFlow(s, t);
if (ans < sum) printf("%d\n", 0);
else {
printf("%d\n", 1);
printPath();
}
return 0;
}

「网络流 24 题」最长递增子序列 - 6

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
//  Created by ZJYelizaveta on 2017年08月24日 星期四 20时02分04秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 500 + 3;
const int MAXNODE = 1000 + 3;
const int INF = 0x3f3f3f3f;
int n;
int a[MAX_N];
int f[MAX_N];
int maxLength;

namespace Dinic {
struct Edge {
int to, cap, rev;
Edge (int to, int cap, int rev) : to(to), cap(cap), rev(rev){}
};
vector<Edge> G[MAXNODE];
int level[MAXNODE], iter[MAXNODE];

inline void clear() {
for (int i = 0; i < MAXNODE; ++i) G[i].clear();
}

inline void addEdge(int from, int to, int cap) {
G[from].push_back(Edge(to, cap, G[to].size()));
G[to].push_back(Edge(from, 0, G[from].size() - 1));
}

bool bfs(int s, int t) {
memset(level, -1, sizeof level);
queue<int> q;
q.push(s), level[s] = 0;

while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return ~level[t];
}

int dfs(int u, int flow, int t) {
if (u == t) return flow;

for (int &i = iter[u]; i < G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap && level[e.to] == level[u] + 1) {
int d = dfs(e.to, min(flow, e.cap), t);
if (d) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}

int maxFlow(int _s, int _t) {
int s = _s, t = _t;
int d = 0, flow = 0;
while (bfs(s, t)) {
memset(iter, 0, sizeof iter);
while (d = dfs(s, INF, t), d) flow += d;
}
return flow;
}
}
using namespace Dinic;

inline int solve1() {
int ans = -INF;
memset(f, 0, sizeof f);
for (register int i = 1; i <= n; ++i) {
f[i] = 1;
for (register int j = 1; j < i; ++j) {
if (a[i] >= a[j]) f[i] = max(f[i], f[j] + 1);
}
ans = max(ans, f[i]);
}
return ans;
}

inline void solve2() {
int s = 0, t = (n << 1) + 1;
for (register int i = 1; i <= n; ++i) {
addEdge(i, i + n, 1);
if (f[i] == 1) addEdge(s, i, 1);
if (f[i] == maxLength) addEdge(i + n, t, 1);

for (register int j = 1; j < i; ++j) {
if (a[j] <= a[i] && f[j] + 1 == f[i]) addEdge(j + n, i, 1);
}
}
int ans = maxFlow(s, t);
printf("%d\n", ans);
}

inline void solve3() {
clear();
int s = 0, t = (n << 1) + 1;
for (register int i = 1; i <= n; ++i) {
int cap = 1;
if (i == 1 || i == n) cap = INF;//

addEdge(i, i + n, cap);
if (f[i] == 1) addEdge(s, i, cap);
if (f[i] == maxLength) addEdge(i + n, t, cap);
for (register int j = 1; j < i; ++j) {
if (a[j] <= a[i] && f[j] + 1 == f[i]) addEdge(j + n, i, 1);
}
}
int ans = maxFlow(s, t);
printf("%d\n", ans);
}

int main()
{
freopen("alis.in", "r", stdin);
freopen("alis.out", "w", stdout);
n = readIn();
for (register int i = 1; i <= n; ++i) a[i] = readIn();
maxLength = solve1();
printf("%d\n", maxLength);
if (maxLength == 1) printf("%d\n%d\n", n, n);
else {
solve2();
solve3();
}
// fprintf(stderr, "Time used : %.3f\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}

「网络流 24 题」试题库 - 7

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
//  Created by ZJYelizaveta on 2017年08月17日 星期四 22时27分08秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
inline int readIn() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 1000 + 3;
const int INF = 0x3f3f3f3f;
int k, n;
int s, t;
int ans, sum;

namespace Dinic {
struct Edge {
int to, cap, rev;
Edge(int to, int cap, int rev) : to(to), cap(cap), rev(rev){}
};
vector<Edge> G[MAX_N << 1];
int iter[MAX_N << 1], level[MAX_N << 1];

inline void addEdge(int from, int to, int cap) {
G[from].push_back(Edge(to, cap, G[to].size()));
G[to].push_back(Edge(from, 0, G[from].size() - 1));
}

bool bfs() {
memset(level, -1, sizeof level);
queue<int> q;
q.push(s), level[s] = 1;

while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return ~level[t];
}

int dfs(int u, int flow) {
if (u == t) return flow;

for (int &i = iter[u]; i < G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap && level[e.to] == level[u] + 1) {
int d = dfs(e.to, min(e.cap, flow));
if (d) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}

int maxFlow(int _s, int _t) {
s = _s, t = _t;
int flow = 0, d = 0;
while (bfs()) {
memset(iter, 0, sizeof iter);
while (d = dfs(s, INF), d) flow += d;
}
return flow;
}
}
using namespace Dinic;

inline void printSolution() {
for (int i = n + 1; i <= n + k; ++i) {
printf("%d:", i - n);
for (int j = 0; j < (int)G[i].size(); ++j) {
Edge &e = G[i][j];
if (e.to <= n && e.to >= 1 && e.cap) printf(" %d", e.to);
}
printf("\n");
}
}

int main()
{
k = readIn(), n = readIn();
s = 0, t = k + n + 1;
sum = 0;
for (int i = 1; i <= k; ++i) {
int num = readIn(); sum += num;
addEdge(i + n, t, num);
}
for (int i = 1; i <= n; ++i) {
int cnt = readIn();
addEdge(s, i, 1);
for (int j = 1; j <= cnt; ++j) {
int type = readIn();
addEdge(i, type + n, 1);
}
}
ans = maxFlow(s, t);
// printf("%d %d\n", ans, sum);
if (ans < sum) printf("No Solution!\n");
else printSolution();
return 0;
}
Partager