网络流24题 I
BGM
晴れゆく空 - RADWIMPS （因为目前都是VIP歌曲所以没链接 QwQ）
BB
狂粉《天气之子》QAQQQ
Introduction
本文包括网络流24题的一部分（因为蒟蒻还没写完QAQ），还有与其有些关联的题目
- 网络流24题
https://www.cnblogs.com/Capella/p/8192729.html - 二分图定理
https://www.cnblogs.com/GuessYCB/p/8331314.html
https://blog.csdn.net/u013043514/article/details/48206577 - 最大权闭合子图
https://blog.csdn.net/can919/article/details/77603353 - 算法合集之《最小割模型在信息学竞赛中的应用》
https://wenku.baidu.com/view/986baf00b52acfc789ebc9a9.html - 二分图最大匹配的König定理及其证明
http://www.matrix67.com/blog/archives/116
飞行员配对方案问题 - luogu P2756
Description
英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。
对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。
Sample Input
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1
Sample Output
4
1 7
2 9
3 8
5 10
Solution - 二分图最大匹配
二分图最大匹配裸题，不放代码 QAQ
太空飞行计划问题 - luogu P2762
Description
W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到的仪器是I的子集RjÍI。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。
Sample Input
2 3
10 1 2
25 2 3
5 6 7
Sample Output
1 2
1 2 3
17
Solution - 最大权闭合子图
最大权闭合子图 指带点权图中，某一个点被选择时，其后继节点一定会需要选择，满足该规则约束下的点权和最大值
在本题中，实验选择时，其所依赖的仪器一定需要被选择，而要求最大化净利润，因此其为最大权闭合子图问题
对于该模型，构图方法如下
S -> { i }, cap = ai (1 <= i <= n, ai >= 0)，对于原图中权值非负的点，从S向改点连接一条容量为权值的边{ i } -> T, cap = |ai| (1 <= i <= n, ai < 0)，对于原图中权值为负的点，从该点向T连接一条容量为权值的绝对值的边{ i } -> { j }, cap = inf (1 <= i, j <= n, i -> j in E)，对于原图中存在的边，边权改为正无穷
答案为正权之和 - 最小割
最后方案为与S连通的点
证明见论文（写的真好QAQ）
以下代码只给出了main函数部分，其余为任意的网络流算法，随便搞个跑跑就行hhh
int main() {
int n, m;
scanf("%d%d", &m, &n);
int ss = 0, tt = n + m + 1;
ll sum = 0;
init(tt);
for(int i = 1; i <= m; i++) {
int v;
scanf("%d", &v);
addEdge(ss, i, v);
addEdge(i, ss, 0);
sum += v;
static char tools[10000];
memset(tools,0,sizeof tools);
cin.getline(tools,10000);
int ulen=0,tool;
while (sscanf(tools+ulen,"%d",&tool)==1) {
addEdge(i, tool + m, inf);
addEdge(tool + m, i, 0);
if (tool==0)
ulen++;
else {
while (tool) {
tool/=10;
ulen++;
}
}
ulen++;
}
}
for(int i = 1; i <= n; i++) {
int v;
scanf("%d", &v);
addEdge(i + m, tt, v);
addEdge(tt, i + m, 0);
}
sum -= ISAP(tt - ss + 1, ss, tt);
used[ss] = true;
dfs(ss);
for(int i = head[ss]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(used[v]) {
printf("%d ", v);
}
}
puts("");
for(int i = head[tt]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(used[v]) {
printf("%d ", v - m);
}
}
puts("");
printf("%lld\n", sum);
}
方格取数问题 - luogu P2774
Description
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
Sample Input
3 3
1 2 3
3 2 3
2 3 1
Sample Output
11
Solution - 二分图最大权独立集
二分图最大独立集 = 点数 - 最小顶点覆盖
二分图最大权独立集 = 点权和 - 最小权顶点覆盖
二分图最小顶点覆盖 = 最大匹配 （König定理）
个人对König定理还比较懵 QvQ，所以不严谨地直观上解释一下1、2式
1、2式实际上是一样的，1式无权，2式带权，故只解释1式
对于1式，要在二分图中选出最大独立集，只需要选择不在最小顶点覆盖集中的顶点即可，他们之间一定没有边，因为若有边，而这两个点不被覆盖，说明该边不被覆盖，矛盾
而这样选择是否是最优的？假设选择的集合是某一个点集的补集，由于独立集需要满足两两点之间没有边，这就意味着原集合需要满足点集覆盖所有边，否则补集会出现至少一个点对之间有边的情况。而最小顶点覆盖恰是满足这一要求的最小集合，因而其补集为最大独立集
废话这么多，本题可以发现是个二分图，需要求其最大权独立集，故答案为点权和 - 最小割
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
int ss = 0, tt = n * m + 1;
ll sum = 0;
init(tt);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int v, u = (i - 1) * m + j;
cin >> v;
sum += v;
if((i + j) & 1) {
addEdge(ss, u, v);
} else {
addEdge(u, tt, v);
}
for(int k = 0; k < 4; k++) {
int nx = i + dx[k], ny = j + dy[k];
if(nx <= 0 || ny <= 0 || nx > n || ny > m) {
continue;
}
v = (nx - 1) * m + ny;
if((i + j) & 1) {
addEdge(u, v, inf);
} else {
addEdge(v, u, inf);
}
}
}
}
cout << (sum - ISAP(tt - ss + 1, ss, tt)) << "\n";
}
骑士共存问题 - luogu P3355
Description
在一个 n*n个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入
-X-X-
X---X
--S--
X---X
-X-X-
对于给定的 n*n 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击
Sample Input
3 2
1 1
3 3
Sample Output
5
Solution - 二分图最大独立集
可以发现这也是个二分图求最大独立集的问题，代码不放了QAQ
圆桌问题 - luogu P3254
Description
假设有来自m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为ri (i =1,2,……,m)。
会议餐厅共有n 张餐桌，每张餐桌可容纳ci (i =1,2,……,n)个代表就餐。
为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。
对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案。
Sample Input
4 5
4 5 3 5
3 5 2 6 4
Sample Output
1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5
Solution - 二分图多重匹配
可以发现，这是算法实验6！（大雾）
单位记为i，餐桌记为j，本题建图为
S -> {i}, cap = ri{j} -> T, cap = cj{i} -> {j}, cap = 1
当最大流为sum(ri)时有解
另外听说本题也可以贪心做，洛谷有题解 QAQ
输出方案时，找满流边即可，不放代码
最小路径覆盖问题 - luogu P2764
Description
给定有向图 G=(V,E) 。设 P 是 G 的一个简单路(顶点不相交)的集合。如果 V 中每个定点恰好在P的一条路上，则称 P 是 G 的一个路径覆盖。P中路径可以从 V 的任何一个定点开始，长度也是任意的，特别地，可以为 0 。G 的最小路径覆盖是 G 所含路径条数最少的路径覆盖。设计一个有效算法求一个 GAP (有向无环图) G 的最小路径覆盖。
Sample Input
11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11
Sample Output
1 4 7 10 11
2 5 8
3 6 9
3
Solution 1 - 最小路径覆盖 - 最小费用最大流
建图：将点u拆为点u与点u'
S -> {u}, cap = 1, cost = 0S -> {u'}, cap = 1, cost = 1{u'} -> T, cap = 1, cost = 0{u} -> {v'} ( (u, v) in E ), cap = 1, cost = 0
可以看出在满流情况下，每一个v'会优先选择u -> v'这条边，其会使得花费更小，实在不行才会选择S -> u'这条边，总花费最小值即为最小路径覆盖
#include <bits/stdc++.h>
#define double long double
using namespace std;
typedef long long ll;
const int N = (int)500 + 3;
const int M = (int)10000 + 3;
const int inf = 1LL << 30;
struct Node {
int u;
ll d;
bool operator < (const Node& b) const {
return d > b.d;
}
};
struct edge {
int v, nxt, flow;
ll cost;
};
int G[N][N];
edge e[M * 4];
int head[N], tot;
int cur[N];
bool used[N];
ll dis[N], h[N];
inline void init() {
memset(head, -1, sizeof(head));
tot = 0;
}
inline void addEdge(int u, int v, int flow, ll cost) {
e[tot] = edge{v, head[u], flow, cost};
head[u] = tot++;
e[tot] = edge{u, head[v], 0, -cost};
head[v] = tot++;
}
bool dijkstra(int src, int des, int n) {
priority_queue<Node> que;
fill(dis + 0, dis + n + 1, inf);
memcpy(cur, head, sizeof(head));
dis[des] = 0;
que.push(Node{des, 0});
while(!que.empty()) {
Node ele = que.top();
que.pop();
int u = ele.u;
ll d = ele.d;
if(d > dis[u]) {
continue;
}
for(int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(e[i^1].flow && dis[v] > dis[u] - e[i].cost + h[u] - h[v]) {
dis[v] = dis[u] - e[i].cost + h[u] - h[v];
que.push(Node{v, dis[v]});
}
}
}
return dis[src] != inf;
}
int dfs(int u, int des, int low, ll& totalCost) {
if(u == des) {
return low;
}
used[u] = true;
int sum = 0;
for(int& i = cur[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
ll du = (dis[u] - h[des] + h[u]);
ll dv = (dis[v] - h[des] + h[v]);
if(!used[v] && e[i].flow && du - e[i].cost == dv) {
int aug = dfs(v, des, min(e[i].flow, low - sum), totalCost);
if(aug) {
e[i].flow -= aug;
e[i ^ 1].flow += aug;
sum += aug;
totalCost += 1LL * aug * e[i].cost;
}
if(sum == low) {
break;
}
}
}
used[u] = false;
return sum;
}
inline pair<int, ll> solve(int src, int des, int n) {
pair<int, ll> pr(0, 0LL);
while(dijkstra(src, des, n)) {
while(true) {
int x = dfs(src, des, inf, pr.second);
pr.first += x;
if(!x) {
break;
}
}
}
return pr;
}
inline void showPath(int u, int n) {
u -= n;
cout << u << " ";
for(int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(v > n && e[i].flow == 0) {
showPath(v, n);
return;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
int n, m;
cin >> n >> m;
int ss = 0, tt = 2 * n + 1;
for(int i = 1; i <= n; i++) {
addEdge(ss, i, 1, 0);
addEdge(i + n, tt, 1, 0);
addEdge(ss, i + n, 1, 1);
}
while(m--) {
int u, v;
cin >> u >> v;
addEdge(u, v + n, 1, 0);
}
auto res = solve(ss, tt, tt - ss + 1);
for(int i = head[ss]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(v > n && e[i].flow == 0) {
showPath(v, n);
cout << "\n";
}
}
cout << res.second << "\n";
}
Solution 2 - 最小路径覆盖
建图：将点u拆为点u与点u'
S -> {u}, cap = 1{u'} -> T, cap = 1{u} -> {v'} ( (u, v) in E ), cap = 1
答案为 点数 - 最大匹配，直观上看每一个匹配意味着u -> v，达到最大匹配说明起点最少
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
int n, m;
cin >> n >> m;
int ss = 0, tt = 2 * n + 1;
for(int i = 1; i <= n; i++) {
addEdge(ss, i, 1);
addEdge(i + n, tt, 1);
}
while(m--) {
int u, v;
cin >> u >> v;
addEdge(u, v + n, 1);
}
int sum = ISAP(tt - ss + 1, ss, tt);
for(int i = 1; i <= n; i++) {
for(int j = head[i]; ~j; j = e[j].nxt) {
if(e[j].val == 0 && e[j].v > n) {
//cout << "?" << i << " -> " << e[j].v - n << endl;
isIn[e[j].v - n] = true;
}
}
}
for(int i = 1; i <= n; i++) {
if(isIn[i] == false) {
showPath(i, n);
cout << "\n";
}
}
cout << n - sum << "\n";
}
魔术球问题 - luogu P2765
Description
«问题描述：
假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，…的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4 根柱子上最多可放11 个球。
«编程任务：
对于给定的n，计算在n根柱子上最多能放多少个球。
Sample Input
4
Sample Output
11
1 8
2 7 9
3 6 10
4 5 11
Solution - 最小路径覆盖
画出图后可以发现，这不是等价于最小路径覆盖咩
有意思的是如何动态求
查了题解后发现可以在原残留网络中动态加点与加边，因为边是新增的，并且连向T，因此流量依旧守恒，因此可以继续跑网络流算法
由于蒟蒻用的是ISAP，因此魔改了ISAP算法使得其适合于动态求，具体见代码
#include <bits/stdc++.h>
#define double long double
using namespace std;
typedef long long ll;
const int N = (int)10000 + 3;
const int M = (int)1e6 + 3;
const int inf = 1LL << 30;
struct edge{
int v, val, nxt;
};
int d[N], head[N], gap[N], cur[N], pre[N];
bool isIn[N];
edge e[M << 1];
int tot;
inline void init(){
memset(head, -1, sizeof(head));
memset(d, 0, sizeof(d));
memset(gap, 0, sizeof(gap));
tot = 0;
}
void addEdge(int u, int v, int val){
e[tot] = edge{v, val, head[u]};
head[u] = tot++;
cur[u] = head[u];
e[tot] = edge{u, 0, head[v]};
head[v] = tot++;
cur[v] = head[v];
}
int ISAP(int n, int src, int des){
int sum = 0;
int u = pre[src] = src;
while(d[src] < n){
if(u == des){
int aug = inf, v;
for(u = pre[des], v = des; v != src; v = u, u = pre[u]) aug = min(aug, e[cur[u]].val);
for(u = pre[des], v = des; v != src; v = u, u = pre[u]){
e[cur[u]].val -= aug;
e[cur[u]^1].val += aug;
}
sum += aug;
continue;
}
bool flag = false;
for(int& i = cur[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(d[u] == d[v] + 1 && e[i].val){
pre[v] = u;
u = v;
flag = true;
break;
}
}
if(!flag){
int mind = n;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(e[i].val && d[v] < mind){
mind = d[v];
cur[u] = i;
}
}
if((--gap[d[u]]) == 0) break;
d[u] = mind + 1;
gap[d[u]]++;
u = pre[u];
}
}
return sum;
}
inline void showPath(int u) {
cout << u << " ";
for(int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(v > 5000 && e[i].val == 0) {
showPath(v - 5000);
return;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
int n;
cin >> n;
int ss = 0, tt = 10000, m = 1, res = 0;
d[tt] = 0;
d[ss] = 3;
while(true) {
int u = m;
addEdge(ss, u, 1);
addEdge(u + 5000, tt, 1);
d[u + 5000] = 1;
d[u] = 2 * m + 3;
for(int i = (int)ceil(sqrt(u)); i * i < 2 * u; i++) {
int j = i * i - u;
if(j > 0 && j < u) {
addEdge(j, u + 5000, 1);
d[j] = 2;
d[ss] = 3;
}
}
res += ISAP(2 * m + 2, ss, tt);
if(m - res > n) {
break;
}
m++;
}
m--;
cout << m << endl;
for(int i = 1; i <= m; i++) {
for(int j = head[i]; ~j; j = e[j].nxt) {
if(e[j].val == 0 && e[j].v > 5000) {
isIn[e[j].v - 5000] = true;
}
}
}
for(int i = 1; i <= m; i++) {
if(isIn[i] == false) {
showPath(i);
cout << "\n";
}
}
}
Plug It In - Gym 101873F
Description
给定n个电器和m个插头，每个电器只能插入一个插头，每个插头只能插入一个电器，同时给出k个关系，每个关系描述插入第j个插头可以插入第i个电器，现在你有一个插排，他可以代替某个插头，并能接受3个电器，问如何安排使得被插入的电器最多
Sample Input
3 6 8
1 1
1 2
1 3
2 3
2 4
3 4
3 5
3 6
Sample Output
5
Solution
本题与魔术球问题类似，不同的地方在于每次枚举的时候不能直接换边，会导致流量不守恒
因此，首先在原图上跑一次最大流，记为sum，然后把这个残余网络备份下来，每次枚举第i个插头时先还原残余网络，在加入一个额外的点连接与第i个插头相连的电器，容量为1，再将其连向T，容量为2，再跑最大流，记为delta，最后答案为max { sum + delta }
#include <bits/stdc++.h>
#define double long double
using namespace std;
typedef long long ll;
const int N = (int)3000 + 15;
const int M = (int)1e6 + 15;
const int inf = 1LL << 30;
struct edge{
int v, val, nxt;
};
int d[N], head[N], gap[N], cur[N], pre[N];
edge e[M << 1];
int tot;
edge me[M << 1];
int mtot;
int md[N], mhead[N], mgap[N], mcur[N], mpre[N];
inline void init(){
memset(head, -1, sizeof(head));
memset(d, 0, sizeof(d));
memset(gap, 0, sizeof(gap));
tot = 0;
}
void addEdge(int u, int v, int val){
e[tot] = edge{v, val, head[u]};
cur[u] = head[u] = tot++;
e[tot] = edge{u, 0, head[v]};
cur[v] = head[v] = tot++;
}
int ISAP(int n, int src, int des){
int sum = 0;
int u = pre[src] = src;
while(d[src] < n){
if(u == des){
int aug = inf, v;
for(u = pre[des], v = des; v != src; v = u, u = pre[u]) aug = min(aug, e[cur[u]].val);
for(u = pre[des], v = des; v != src; v = u, u = pre[u]){
e[cur[u]].val -= aug;
e[cur[u]^1].val += aug;
}
sum += aug;
continue;
}
bool flag = false;
for(int& i = cur[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(d[u] == d[v] + 1 && e[i].val){
pre[v] = u;
u = v;
flag = true;
break;
}
}
if(!flag){
int mind = n;
for(int i = head[u]; ~i; i = e[i].nxt){
int v = e[i].v;
if(e[i].val && d[v] < mind){
mind = d[v];
cur[u] = i;
}
}
if((--gap[d[u]]) == 0) break;
d[u] = mind + 1;
gap[d[u]]++;
u = pre[u];
}
}
return sum;
}
inline void backup() {
mtot = tot;
memcpy(me, e, tot * sizeof(edge));
memcpy(md, d, sizeof(d));
memcpy(mhead, head, sizeof(head));
memcpy(mgap, gap, sizeof(gap));
memcpy(mcur, cur, sizeof(cur));
memcpy(mpre, pre, sizeof(pre));
}
inline void recover() {
mtot = tot;
memcpy(e, me, tot * sizeof(edge));
memcpy(d, md, sizeof(d));
memcpy(head, mhead, sizeof(head));
memcpy(gap, mgap, sizeof(gap));
memcpy(cur, mcur, sizeof(cur));
memcpy(pre, mpre, sizeof(pre));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
int n, m, k;
cin >> m >> n >> k;
int ss = 0, tt = n + m + 2;
for(int i = 1; i <= n; i++) {
addEdge(ss, i, 1);
}
for(int i = 1; i <= m; i++) {
addEdge(i + n, tt, 1);
}
while(k--) {
int u, v;
cin >> v >> u;
addEdge(u, v + n, 1);
}
gap[0] = tt - 1;
int sum = ISAP(tt - ss, ss, tt), ans = 0;
backup();
for(int i = n + 1; i <= n + m; i++) {
addEdge(tt - 1, tt, 2);
d[tt - 1] = 1;
gap[1]++;
for(int j = head[i]; ~j; j = e[j].nxt) {
int v = e[j].v;
if(v >= 1 && v <= n) {
addEdge(v, tt - 1, 1);
gap[d[v]]--;
d[v] = 2;
gap[2]++;
}
}
ans = max(ans, sum + ISAP(tt - ss + 1, ss, tt));
recover();
}
cout << ans << "\n";
}
