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

失踪人口回归!

「网络流 24 题」方格取数 - 9

建图太神啦QAQ
二分图点权最大独立集,转化为最小割模型,从而用最大流解决。
贴几个结论和定义,如果不知道可以看一下

最小点权覆盖集:满足每一条边的两个端点至少选一个的最小权点集。
最大点权独立集:满足每一条边的两个端点最多选一个的最大权点集。
最小点权覆盖 = 原图最小割
最大点权独立集 = 总点权 - 最小点权覆盖 = 总点权 - 最小割 = 总点权 - 最大流

我们将棋盘黑白染色,发现只有不同颜色的格子,是不能同时选择的。将每个格子看作一个点,如果我们将有冲突的格子之间连边的话,会发现这是一个二分图。

  • 我们将染成黑色的格子归为$A$集合,染成白色的格子归为$B$集合
  • 建立超级源点$s$连向$A$集合中的每一个点,边的容量为格子中的数值; 建立超级汇点$t$,$B$集合中的每一个点向$t$连一条容量为格子中数值中的边
  • 对于一个染成黑色的格子,向与它相邻的白色格子连一条容量为$INF$的边
  • $ans = sum - maxFlow(s, t)$

我们可以发现,我们需要求出最小的流量使得$A$集合与$B$集合不联通,相当于求此图的最小割,而此图的最小割就是原图的最小点权覆盖集,二分图最小点权覆盖集的补集就是二分图的最大点权独立集。

「网络流 24 题」餐巾计划 - 10

开始做费用流的题目啦QAQ
这个问题的主要约束条件是每天的餐巾够用,经过分析可以把每天要用的和用完的分离开处理,建模后就是二分图
。二分图$A$集合中顶点$A_{i}$表示第$i$天用完的餐巾,其数量为$r_{i}$,所以从$s$向$A_{i}$连接容量为$r_{i}$的边作为限制。$B$集合中每个点$B_{i}$则是第$i$天需要的餐巾,数量为$r_{i}$,与$t$连接的边容量作为限制。

具体建模型方法如下:

  • 将每一天拆分为$A$集合中的顶点$A_{i}$和$B$集合中的顶点$B_{i}$
  • 建立超级源点$s$向$A$集合中的每一个点连一条容量为$r_{i}$,费用为$0$的边 ; 建立超级源点$t$,$B$集合中的每一个点向$t$连一条容量为$r_{i}$,费用为$0$的边
  • 新购买餐巾,从$s$向$B$集合中的每一个点连一条容量$\infty$,费用为$p$的边。
  • 每天用完的餐巾可以选择留到下一天,从每个$A_{i}$向$A_{i+1}(i+1 \leq N)$连一条容量为$\infty$,费用为$0$的边。
  • 送到快洗部,从每个$A_{i}$向$B_{i+m}(i+m \leq N)$连一条容量为$\infty$,费用为$f$的边。
  • 送到慢洗部,从每个$A_{i}$向$B{i+n}(i+n \leq N)$连一条容量为$\infty$,费用为$s$的有向边。

「网络流 24 题」航空路线问题 - 11

LOJ上最后一道网络流,脑抽了,调了很久的输出方案QAQ
建模如下:

  • 将每个点拆分为两个集合,$A$集合和$B$集合
  • 从$A$集合的$A_{i}$向$B$集合中的$B_{i}$连一条容量为$1$费用为$-1$的边$(1 < i < n)$
  • 从$A_{1}$向$B_{1}$连一条容量为$2$,费用为$-1$的边
  • 从$A_{n}$向$B_{n}$连一条容量为$2$,费用为$-1$的边
  • 如果存在边$(i,j), i<j$,那么从$B_{i}$向$A_{j}$连一条容量$1$,费用为$0$的边
  • 跑一遍最小费用最大流,若$A_{1} \sim B_{1}$满流,则存在解,否则无解

「网络流 24 题」软件补丁 - 12

通过状压转换成为最短路问题

好像跟[CTSC 1999]补丁VS错误这道题目是一样的但是当时没意识到这是一个费用流的题QAQ,然后按照原来的写了一遍交上去,结果跑得贼慢,然后虚心的学习了一下别人的代码,发现,诶怎么不用加边呀QAQ

我们可以肯定最多只有$2^{n}$种错误情况 ( 若这是第$i$个错误则用二进制表示时这一位为$0$ ),初始状态为$2^{n}−1$, 最后要求达到的状态是$0$。
进一步我们发现$n$实际上很小,可以状压,那么可以想到用二进制来表示出所有的错误情况。
但是实际上根本不用建图呀,每一次判断当前的补丁是否可用 (和是否加边的判断是一样的) ,然后状压跑一遍$SPFA$就行了QAQ

「网络流 24 题」星际转移问题 - 13

真的贼难调QAQ,需要按照时间来拆点,见识了

我们把网络优化问题转化为枚举答案 $+$可行性判定问题。
枚举天数,按天数把图分层,因为乘船每坐一站天数都要增加$1$,把太空船航线抽象成图中的一条边,跨图的两层。由于太空船容量有限,边上也要加上容量限制。
除了坐船以外,人还可以在某个空间站等待下一班太空船的到来,所以每个点要与下一层同一点连接一条容量为$\infty$的边。这样在层限制的图上求出的网络最大流就是在当前天数以内能够从地面到月球的最多的人数,该人数随天数递增不递减,存在单调性。所以可以枚举答案或二分答案,用网络流判定。网络流判定问题更适合枚举答案,而不是二分,因为新增一些点和边只需要在原有的基础上增广,不必重新求网络流。(转自 Byvoid)

  • 首先判断地球到月球之间是否存在一条可行道路,若不存在,那么无解;否则把每一个太空站按照天数拆分成为$d$个点,$[i, d]$表示第$i$个站第$d$天。建立超级源点$s$和超级汇点$t$,并顺序枚举天数(网络流相比二分更适合顺序枚举)
  • 对于第$d$天,从$s$向$[0, d]$连一条容量为$\infty$的边。
  • 对于第$d$天,从$[-1, d]$向$t$连一条容量为$\infty$的边
  • 对于第$i$艘飞船,令其第$d - 1$天在$a$处,第$d$天在$b$处,则从$[a, d - 1]$向$[b, d]$连一条容量为该太空飞船容量的边
  • 对于第$i$个太空站,从$[i, d - 1]$向$[i, d]$连一条容量为$\infty$的边
  • 求最大流,若$ans = k$则停止枚举,那么当前的$d$就为答案

「网络流 24 题」孤岛营救问题 - 14

转化为分层图最短路问题。

用一个$p$位二进制串表示当前获得的钥匙状态(若获得则二进制串中的这一位为$1$),那么我们需要建立$2^{p}$层图。每层图表示在当前钥匙状态下的地图,每获得一把钥匙进入新的一层,然后i跑一次最短路即可。
分层图最短路可以看这一个BZOJ 2763: [JLOI2011]飞行路线

「网络流 24 题」汽车加油行驶问题 - 15

依然是分层图最短路QAQ

「网络流 24 题」数字梯形 - 16

最大权不相交路径问题转化为最大费用最大流模型

  • 梯形的顶至底的$m$条路径互不相交,说明了每个点只能经过一次,所以这里限制条件就是点,建图方法如下 :

    • 将一个点拆分为两个点一个在$A$集合,一个在$B$集合(限制点流量)
    • 建立超级源点$s$向梯形顶层每一个在合中的点连一条容量为$1$,费用为$0$的边
    • 建立超级汇点$t$,从梯形底层每一个在$B$集合中的点向$t$连一条容量为$1$,费用为$0$的边
    • $A_{i, j}$向$B_{i, j}$连一条容量为$1$,费用为当前该点在数字梯形中对应的权值(这里权值取负)的边
    • 从$B_{i, j}$向$A_{i + 1, j}$,$A_{i + 1, j + 1}$连一条容量为$1$,费用为$0$的边
    • 跑一遍最小费用最大流,答案取反
  • 梯形的顶至底的 $m$条路径仅在数字结点处相交,这时点上没有任何限制,而限制在边

    • 建立超级源点$s$向梯形顶层每一个在$A$集合中的点连一条容量为$1$,费用为$0$的边
    • 建立超级汇点$t$,从梯形底层每一个在$A$集合中的点向$t$连一条容量为$\infty$,费用为$0$的边
    • $A_{i, j}$向$B_{i, j}$连一条容量为$\infty$,费用为当前该点在数字梯形中对应的权值(这里权值取负)的边
    • 从$B_{i, j}$向$A_{i + 1, j}$,$A_{i + 1, j + 1}$连一条容量为$1$,费用为$0$的边(限制边流量)
    • 跑一遍最小费用最大流,答案取反
  • 梯形的顶至底的$m$条路径允许在数字结点相交或边相交,这时点边都没有限制

    • 建立超级源点$s$向梯形顶层每一个在合中的点连一条容量为$1$,费用为$0$的边
    • 建立超级汇点$t$,从梯形底层每一个在$A$集合中的点向$t$连一条容量为$\infty$,费用为$0$的边
    • $A_{i, j}$向$B_{i, j}$连一条容量为$\infty$,费用为当前该点在数字梯形中对应的权值(这里权值取负)的边
    • 从$B_{i, j}$向$A_{i + 1, j}$,$A_{i + 1, j + 1}$连一条容量为$\infty$,费用为$0$的边
    • 跑一遍最小费用最大流,答案取反

「网络流 24 题」运输问题 - 17

费用流问题裸题QAQ
建模方法一如既往的很套路:

  • $m$ 个仓库做为$A$集合, $n$个零售商店做为$B$集合。
  • 建立超级源点$s$向$A$集合中的每一个点连一条容量为$a[i]$,费用为$0$的边;建立超级汇点$t$,$B$集合中的每一个点向$t$连一条容量为$b[i]$,费用为$0$的边。
  • 从$A$集合中的点$A_{i}$向$B$集合中的点$B_{j}$连一条容量为$\infty$,费用为$c[i][j]$的边
  • 最小总效益跑一遍最小费用最大流,最大总效益跑一遍最大费用最大流(与$16$题一样,把费用取负就可以了)。

「网络流 24 题」分配问题 - 18

和$17$题一样还是费用流问题裸题QAQ
建模方法一如既往的很套路:

  • $n$ 个人做为$A$集合, $n$个任务做为$B$集合。
  • 建立超级源点$s$向$A$集合中的每一个点连一条容量为$1$,费用为$0$的边;建立超级汇点$t$,$B$集合中的每一个点向$t$连一条容量为$1$,费用为$0$的边。
  • 从$A$集合中的点$A_{i}$向$B$集合中的点$B_{j}$连一条容量为$\infty$,费用为$c[i][j]$的边
  • 最小总效益跑一遍最小费用最大流,最大总效益跑一遍最大费用最大流(与$16$题一样,把费用取负就可以了)。

代码

「网络流 24 题」方格取数 - 9

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
//  Created by ZJYelizaveta on 2017年08月18日 星期五 19时52分22秒
// 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 = 900 + 3;
const int MAX_M = 30 + 3;
const int INF = 0x3f3f3f3f;
int m, n; // hang, lie
int s, t;
int a[MAX_M][MAX_M];
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 d = 0, flow = 0;
while (bfs()) {
memset(iter, 0, sizeof iter);
while (d = dfs(s, INF), d) flow += d;
}
return flow;
}

}
using namespace Dinic;

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

int main()
{
n = readIn(), m = readIn();
s = 0, t = n * m + 1;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int num = readIn(); sum += num;
int curId = getId(i, j);
// printf("%d\n", curId);
bool flag = (i + j) & 1;
if (flag) addEdge(s, curId, num);
else addEdge(curId, t, num);

if (flag) {
if (i - 1 >= 1) addEdge(curId, getId(i - 1, j), INF);
if (i + 1 <= n) addEdge(curId, getId(i + 1, j), INF);
if (j - 1 >= 1) addEdge(curId, getId(i, j - 1), INF);
if (j + 1 <= m) addEdge(curId, getId(i, j + 1), INF);
}
}
}
ans = maxFlow(s, t);
printf("%d\n", sum - ans);
}

「网络流 24 题」餐巾计划 - 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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
//  Created by ZJYelizaveta on 2017年08月19日 星期六 23时01分39秒
// 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;

namespace MCMF {
struct Edge {
int to, cap, cost, rev;
Edge(int to, int cap, int cost, int rev) : to(to), cap(cap), cost(cost), rev(rev){}
};
vector<Edge> G[MAX_N << 1];
int dist[MAX_N << 1];
int prevV[MAX_N << 1], prevE[MAX_N << 1];
bool inq[MAX_N << 1];

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

pair<int, int> minCostMaxFlow(int s, int t) {
pair<int, int> ans(0, 0);
while (1) {
memset(inq, 0, sizeof inq);
memset(dist, INF, sizeof dist);

deque<int> q;
q.push_front(s), inq[s] = 1, dist[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop_front();
inq[u] = 0;//
for (int i = 0; i < (int)G[u].size(); i++){
Edge &e = G[u][i];
if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
dist[e.to] = dist[u] + e.cost;
prevE[e.to] = i; prevV[e.to] = u;
if (!inq[e.to]) {//
inq[e.to] = 1;
if (q.empty() || dist[e.to] > dist[q.front()]) q.push_back(e.to);//
else q.push_front(e.to);//
}
}
}
}
if (dist[t] == INF) break;

int flow = INF;
for (int i = t; i != s; i = prevV[i]) flow = min(flow, G[prevV[i]][prevE[i]].cap);
ans.first += flow, ans.second += flow * dist[t];

for (int i = t; i != s; i = prevV[i]) {
Edge &e = G[prevV[i]][prevE[i]];
e.cap -= flow;
G[e.to][e.rev].cap += flow;
}
}
return ans;
}
}
using namespace MCMF;

int main()
{
int n = readIn(), P = readIn(), M = readIn(), F = readIn(), N = readIn(), S = readIn();
int s = 0, t = 2 * n + 1;

for (int i = 1; i <= n; ++i) {
int r = readIn();
addEdge(s, i + n, r, 0); addEdge(i, t, r, 0);
addEdge(s, i, INF, P);
if (i + 1 <= n) addEdge(i + n, i + n + 1, INF, 0);
if (i + M <= n) addEdge(i + n, i + M, INF, F);
if (i + N <= n) addEdge(i + n, i + N, INF, S);
}
pair<int, int> ans = minCostMaxFlow(s, t);
printf("%d\n", ans.second);
return 0;
}

「网络流 24 题」航空路线问题 - 11

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
//  Created by ZJYelizaveta on 2017年08月23日 星期三 22时19分32秒
// 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 MAXNODE = 200 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
int s, t;
char str[MAX_N][15 + 3], s1[15 + 3], s2[15 + 3];
map<string, int> M;

namespace MCMF {
struct Edge {
int to, cap, cost, rev;
Edge(int to, int cap, int cost, int rev) : to(to), cap(cap), cost(cost), rev(rev){}
};
vector<Edge> G[MAXNODE];
int dist[MAXNODE];
int prevV[MAXNODE], prevE[MAXNODE];
bool inq[MAXNODE];

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

pair<int, int> minCostMaxFlow() {
pair<int, int> ans(0, 0);
while (1) {
memset(inq, false, sizeof inq);
memset(dist, INF, sizeof dist);
deque<int> q;
q.push_front(s); inq[s] = true, dist[s] = 0;

while (!q.empty()) {
int u = q.front(); q.pop_front();
inq[u] = false;
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {//
dist[e.to] = dist[u] + e.cost;
prevE[e.to] = i; prevV[e.to] = u;
if (!inq[e.to]) {
inq[e.to] = true;//
if (q.empty() || dist[e.to] > dist[q.front()]) q.push_back(e.to);
else q.push_front(e.to);
}
}
}
}
if (dist[t] == INF) break;

int flow = INF;
for (int i = t; i != s; i = prevV[i]) flow = min(flow, G[prevV[i]][prevE[i]].cap);
ans.first += flow, ans.second -= flow * dist[t];

for (int i = t; i != s; i = prevV[i]) {
Edge &e = G[prevV[i]][prevE[i]];
e.cap -= flow;
G[e.to][e.rev].cap += flow;
}
}
return ans;
}
}
using namespace MCMF;

int vis[MAXNODE];
vector<string> vec;
void dfs(int u, int n) {
vis[u] = 1;
for (int i = 0, v; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (!vis[v = e.to] && ((!e.cap && e.cost <= 0) || (e.cap && e.cost >= 0))) {
dfs(v, n);
if (v <= n) vec.push_back(str[v]);
}
}
}

inline void printPath() {
memset(vis, 0, sizeof vis);
vec.clear();
vec.push_back(str[1]);
dfs(1, n);
vec.push_back(str[1]);
for (int i = (int)vec.size() - 1; i >= 0; --i) cout << vec[i] << endl;
}

int main()
{
n = readIn(), m = readIn();

M.clear();
s = 0, t = n * 2 + 1;
for (int i = 1; i <= n; ++i) {
scanf("%s", str[i]);
M[str[i]] = i;
if (i == 1 || i == n) addEdge(i, i + n, 2, 0);
else addEdge(i, i + n, 1, 0);
}
addEdge(s, 1, 2, 0); addEdge(n * 2, t, 2, 0);
for (int i = 1; i <= m; ++i) {
scanf("%s", s1); scanf("%s", s2);
int a = M[s1], b = M[s2];
if (a > b) swap(a, b);
if (a == 1 && b == n) addEdge(a + n, b, 2, -1);
addEdge(a + n, b, 1, -1);
}
pair<int, int> ans = minCostMaxFlow();
if (ans.first != 2) printf("No Solution!\n");
else {
printf("%d\n", ans.second);
printPath();
}
return 0;
}

「网络流 24 题」软件补丁 - 12

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
//  Created by ZJYelizaveta on 2017年08月20日 星期日 09时47分57秒
// 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 = (1 << (17 + 3));
const int INF = 0x3f3f3f3f;
int n, m, s, t;
int w[MAX_N];
char str1[MAX_N], str2[MAX_N];
struct Limited {
int s1, s2, t1, t2; //b+, b-, f+, f-
}lim[100 + 3];
int dist[MAX_N];
bool inq[MAX_N];

inline bool check(int u, int id) {
if ((u | lim[id].s1) != u) return false;
if (u & lim[id].s2) return false;
return true;
}

inline void SPFA() {
memset(inq, false, sizeof inq);
memset(dist, INF, sizeof dist);
queue<int> q;
q.push(s); inq[s] = true; dist[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
inq[u] = false;
for (register int i = 0; i < m; ++i) {
if (check(u, i)) {
int to = (u & (~lim[i].t2)) | lim[i].t1;
if (dist[to] > dist[u] + w[i]) {
dist[to] = dist[u] + w[i];
if (!inq[to]) {
inq[to] = true; q.push(to);
}
}
}
}
}
if (dist[t] == INF) printf("%d\n", 0);
else printf("%d\n", dist[t]);
}
int main()
{
n = readIn(), m = readIn();
s = (1 << n) - 1, t = 0;
for (register int i = 0; i < m; ++i) {
w[i] = readIn();
scanf("%s", str1);
for (register int j = 0; j < n; ++j) {
if (str1[j] == '+') lim[i].s1 |= (1 << j);
else if (str1[j] == '-') lim[i].s2 |= (1 << j);
}
scanf("%s", str2);
for (register int j = 0; j < n; ++j) {
if (str2[j] == '+') lim[i].t1 |= (1 << j);
else if (str2[j] == '-') lim[i].t2 |= (1 << j);
}
}
SPFA();
return 0;
}

「网络流 24 题」星际转移问题 - 13

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
//  Created by ZJYelizaveta on 2017年08月22日 星期二 19时53分41秒
// 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 = 13 + 3;
const int MAX_M = 20 + 3;
const int MAX_K = 50 + 3;
const int MAXNODE = 500000 + 3;
const int INF = 0x3f3f3f3f;
int n, m, k;
int h[MAX_M], r[MAX_M], a[MAX_M][MAX_N];
int s, t;

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 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;

namespace unionFindSet {
int fa[MAX_N];

inline void prepare() {
for (int i = 1; i < MAX_N; ++i) fa[i] = i;
}

inline int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
}
using namespace unionFindSet;

inline int ID(int station, int day) {
return day * (n + 2) + station;
}

inline void solve() {
int moon = 1, earth = 2;
int cur = 0, ans = 0;
addEdge(s, ID(earth, 0), k), addEdge(ID(moon, 0), t, 0);
while (1) {
++cur;
for (int i = 1; i <= n + 2; ++i) {
addEdge(ID(i, cur - 1), ID(i, cur), INF);
}
for (int i = 1; i <= m; ++i) {
addEdge(ID(a[i][(cur - 1) % r[i]], cur - 1), ID(a[i][cur % r[i]], cur), h[i]);
}
addEdge(ID(moon, cur), t, INF);
ans += maxFlow(s, t);
if (ans == k) {
printf("%d\n", cur); break;
}
}
}

int main()
{
n = readIn(), m = readIn(), k = readIn();
prepare();
s = 0, t = n * (n + 2) * (m + 1) * k * 2 + 1;
for (int i = 1; i <= m; ++i) {
h[i] = readIn(), r[i] = readIn();
for (int j = 0; j < r[i]; ++j) {
a[i][j] = readIn() + 2;
// printf("%d ", b[i][j]);
if (j) {
int x = find(a[i][j - 1]);
int y = find(a[i][j]);
// printf("%d %d\n", x, y);
if (x != y) fa[x] = y;
}
}
// printf("\n");
}
int moon = 1, earth = 2;
if (find(earth) != find(moon)) printf("%d\n", 0);
else solve();
return 0;
}

「网络流 24 题」孤岛营救问题 - 14

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
//  Created by ZJYelizaveta on 2017年08月23日 星期三 17时56分49秒
// 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 = 10 + 3;
const int MAX_K = 150 + 3;
const int INF = 0x3f3f3f3f;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int n, m, p, k, s;
int x2[MAX_K], x3[MAX_K], y2[MAX_K], y3[MAX_K], g[MAX_K];
int x[MAX_K], y[MAX_K], q[MAX_K];
int key[MAX_N][MAX_N], d[MAX_N][MAX_N][MAX_N][MAX_N];
bool vis[1024 + 3][MAX_N][MAX_N];

struct Node {
int x, y, st, dist;
Node (int x, int y, int st, int dist) : x(x), y(y), st(st), dist(dist){}
};
queue<Node> Q;

inline void solve() {
Q.push(Node(1, 1, 0, 0));
vis[0][1][1] = true;
while (!Q.empty()) {
Node cur = Q.front(); Q.pop();
for (int i = 0; i <= 3; ++i) {
int x = cur.x + dx[i] , y = cur.y + dy[i] , t = d[cur.x][cur.y][x][y];
if (x >= 1 && x <= n && y >= 1 && y <= m && t != -1 && !( ( cur.st ^ t ) & t )) {
Node next = Node(x, y, (cur.st | key[x][y]), cur.dist + 1);
if( x == n && y == m ) {
printf("%d\n", next.dist); return;
}
if (vis[next.st][x][y]) continue;
vis[next.st][x][y] = true;
Q.push(next);
}
}
}
printf("%d\n", -1);
}

int main()
{
n = readIn(), m = readIn(), p = readIn(), k = readIn();
for (int i = 1; i <= k; ++i) x2[i] = readIn(), y2[i] = readIn(), x3[i] = readIn(), y3[i] = readIn(), g[i] = readIn();
s = readIn();
for (int i = 1; i <= s; ++i) x[i] = readIn(), y[i] = readIn(), q[i] = readIn();

for (int i = 1; i <= k; ++i) {
int &a = d[x2[i]][y2[i]][x3[i]][y3[i]];
int &b = d[x3[i]][y3[i]][x2[i]][y2[i]];
if (a == -1) continue;
if (g[i] == 0) a = b = -1;
else a = b = (a | (1 << (g[i] - 1)));
}
for (int i = 1; i <= s; ++i) key[x[i]][y[i]] |= (1 << (q[i] - 1));
solve();
return 0;
}

「网络流 24 题」汽车加油行驶问题 - 15

「网络流 24 题」数字梯形 - 16

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
150
151
152
153
154
155
//  Created by ZJYelizaveta on 2017年08月20日 星期日 19时21分21秒
// 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 = 20 + 3;
const int MAXNODE = 800 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
int a[MAX_N][MAX_N], num[MAX_N][MAX_N];
int cnt;

namespace MCMF {
struct Edge {
int to, cap, cost, rev;
Edge(int to, int cap, int cost, int rev) : to(to), cap(cap), cost(cost), rev(rev){}
};
vector<Edge> G[MAXNODE];
int dist[MAXNODE];
int prevV[MAXNODE], prevE[MAXNODE];
bool inq[MAXNODE];

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

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

pair<int, int> minCostMaxFlow(int s, int t) {
pair<int, int> ans(0, 0);
while (1) {
memset(inq, 0, sizeof inq);
memset(dist, INF, sizeof dist);

deque<int> q;
q.push_front(s), inq[s] = 1, dist[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop_front();
inq[u] = 0;//
for (int i = 0; i < (int)G[u].size(); i++){
Edge &e = G[u][i];
if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
dist[e.to] = dist[u] + e.cost;
prevE[e.to] = i; prevV[e.to] = u;
if (!inq[e.to]) {//
inq[e.to] = 1;
if (q.empty() || dist[e.to] > dist[q.front()]) q.push_back(e.to);//
else q.push_front(e.to);//
}
}
}
}
if (dist[t] == INF) break;

int flow = INF;
for (int i = t; i != s; i = prevV[i]) flow = min(flow, G[prevV[i]][prevE[i]].cap);
ans.first += flow, ans.second += flow * dist[t];

for (int i = t; i != s; i = prevV[i]) {
Edge &e = G[prevV[i]][prevE[i]];
e.cap -= flow;
G[e.to][e.rev].cap += flow;
}
}
return ans;
}
}
using namespace MCMF;

inline void solve1() {
init();
int s = 0, t = 2 * cnt + 1;
// printf("%d %d %d\n", s, t, cnt);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i + m; ++j) {
addEdge(num[i][j], num[i][j] + cnt, 1, -a[i][j]);
if (i + 1 <= n) {
addEdge(num[i][j] + cnt, num[i + 1][j], 1, 0);
addEdge(num[i][j] + cnt, num[i + 1][j + 1], 1, 0);
}
}
}
for (int i = 1; i <= m; ++i) addEdge(s, num[1][i], 1, 0);
for (int i = 1; i < n + m; ++i) addEdge(num[n][i] + cnt, t, 1, 0);
pair<int, int> ans = minCostMaxFlow(s, t);
printf("%d\n", -ans.second);
}

inline void solve2() {
init();
int s = 0, t = 2 * cnt + 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i + m; ++j) {
addEdge(num[i][j], num[i][j] + cnt, INF, -a[i][j]);
if (i + 1 <= n) {
addEdge(num[i][j] + cnt, num[i + 1][j], 1, 0);
addEdge(num[i][j] + cnt, num[i + 1][j + 1], 1, 0);
}
}
}
for (int i = 1; i <= m; ++i) addEdge(s, num[1][i], 1, 0);
for (int i = 1; i < n + m; ++i) addEdge(num[n][i] + cnt, t, INF, 0);
pair<int, int> ans = minCostMaxFlow(s, t);
printf("%d\n", -ans.second);
}

inline void solve3() {
init();
int s = 0, t = 2 * cnt + 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i + m; ++j) {
addEdge(num[i][j], num[i][j] + cnt, INF, -a[i][j]);
if (i + 1 <= n) {
addEdge(num[i][j] + cnt, num[i + 1][j], INF, 0);
addEdge(num[i][j] + cnt, num[i + 1][j + 1], INF, 0);
}
}
}
for (int i = 1; i <= m; ++i) addEdge(s, num[1][i], 1, 0);
for (int i = 1; i < n + m; ++i) addEdge(num[n][i] + cnt, t, INF, 0);
pair<int, int> ans = minCostMaxFlow(s, t);
printf("%d\n", -ans.second);
}


int main()
{
m = readIn(), n = readIn();
cnt = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i + m; ++j) {
a[i][j] = readIn();
num[i][j] = ++cnt;
// printf("%d %d ", num[i][j], a[i][j]);
}
// printf("\n");
}
solve1();
solve2();
solve3();
return 0;
}

「网络流 24 题」运输问题 - 17

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 Monday, August 21, 2017 AM09:07:18 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 MAXNODE = 200 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
int a[MAX_N], b[MAX_N], c[MAX_N][MAX_N];

namespace MCMF {
struct Edge {
int to, cap, cost, rev;
Edge(int to, int cap, int cost, int rev) : to(to), cap(cap), cost(cost), rev(rev){}
};
vector<Edge> G[MAXNODE];
int dist[MAXNODE];
int prevV[MAXNODE], prevE[MAXNODE];
bool inq[MAXNODE];

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

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

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

pair<int, int> minCostMaxFlow(int s, int t) {
pair<int, int> ans(0, 0);
while (1) {
memset(inq, 0, sizeof inq);
memset(dist, INF, sizeof dist);

deque<int> q;
q.push_front(s), inq[s] = 1, dist[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop_front();
inq[u] = 0;//
for (int i = 0; i < (int)G[u].size(); i++){
Edge &e = G[u][i];
if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
dist[e.to] = dist[u] + e.cost;
prevE[e.to] = i; prevV[e.to] = u;
if (!inq[e.to]) {//
inq[e.to] = 1;
if (q.empty() || dist[e.to] > dist[q.front()]) q.push_back(e.to);//
else q.push_front(e.to);//
}
}
}
}
if (dist[t] == INF) break;

int flow = INF;
for (int i = t; i != s; i = prevV[i]) flow = min(flow, G[prevV[i]][prevE[i]].cap);
ans.first += flow, ans.second += flow * dist[t];

for (int i = t; i != s; i = prevV[i]) {
Edge &e = G[prevV[i]][prevE[i]];
e.cap -= flow;
G[e.to][e.rev].cap += flow;
}
}
return ans;
}
}
using namespace MCMF;

inline void solve1() {
clear();
int s = 0, t = n + m + 1;
for (int i = 1; i <= n; ++i) addEdge(s, i, a[i], 0);
for (int i = 1; i <= m; ++i) addEdge(i + n, t, b[i], 0);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) addEdge(i, j + n, INF, c[i][j]);
pair<int, int> ans = minCostMaxFlow(s, t);
printf("%d\n", ans.second);
}

inline void solve2() {
clear();
int s = 0, t = n + m + 1;
for (int i = 1; i <= n; ++i) addEdge(s, i, a[i], 0);
for (int i = 1; i <= m; ++i) addEdge(i + n, t, b[i], 0);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) addEdge(i, j + n, INF, -c[i][j]);
pair<int, int> ans = minCostMaxFlow(s, t);
printf("%d\n", -ans.second);
}

int main()
{
n = readIn(), m = readIn();
for (int i = 1; i <= n; ++i) a[i] = readIn();
for (int i = 1; i <= m; ++i) b[i] = readIn();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) c[i][j] = readIn();
solve1();
solve2();
return 0;
}

「网络流 24 题」分配问题 - 18

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
//  Created by ZJYelizaveta on Monday, August 21, 2017 AM09:56:23 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 MAXNODE = 200 + 3;
const int INF = 0x3f3f3f3f;
int n;
int c[MAX_N][MAX_N];

namespace MCMF {
struct Edge {
int to, cap, cost, rev;
Edge(int to, int cap, int cost, int rev) : to(to), cap(cap), cost(cost), rev(rev){}
};
vector<Edge> G[MAXNODE];
int dist[MAXNODE];
int prevV[MAXNODE], prevE[MAXNODE];
bool inq[MAXNODE];

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

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

pair<int, int> minCostMaxFlow(int s, int t) {
pair<int, int> ans(0, 0);
while (1) {
memset(inq, false, sizeof inq);
memset(dist, INF, sizeof dist);
deque<int> q;
q.push_front(s); inq[s] = true, dist[s] = 0;

while (!q.empty()) {
int u = q.front(); q.pop_front();
inq[u] = false;
for (int i = 0; i < (int)G[u].size(); ++i) {
Edge &e = G[u][i];
if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {//
dist[e.to] = dist[u] + e.cost;
prevE[e.to] = i; prevV[e.to] = u;
if (!inq[e.to]) {
inq[e.to] = true;//
if (q.empty() || dist[e.to] > dist[q.front()]) q.push_back(e.to);
else q.push_front(e.to);
}
}
}
}
if (dist[t] == INF) break;

int flow = INF;
for (int i = t; i != s; i = prevV[i]) flow = min(flow, G[prevV[i]][prevE[i]].cap);
ans.first += flow, ans.second += flow * dist[t];

for (int i = t; i != s; i = prevV[i]) {
Edge &e = G[prevV[i]][prevE[i]];
e.cap -= flow;
G[e.to][e.rev].cap += flow;
}
}
return ans;
}
}
using namespace MCMF;

inline void solve1() {
clear();
int s = 0, t = n * 2 + 1;
for (int i = 1; i <= n; ++i) addEdge(s, i, 1, 0);
for (int i = 1; i <= n; ++i) addEdge(i + n, t, 1, 0);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) addEdge(i, j + n, INF, c[i][j]);
pair<int, int> ans = minCostMaxFlow(s, t);
printf("%d\n", ans.second);
}

inline void solve2() {
clear();
int s = 0, t = n * 2 + 1;
for (int i = 1; i <= n; ++i) addEdge(s, i, 1, 0);
for (int i = 1; i <= n; ++i) addEdge(i + n, t, 1, 0);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) addEdge(i, j + n, INF, -c[i][j]);
pair<int, int> ans = minCostMaxFlow(s, t);
printf("%d\n", -ans.second);
}

int main()
{
n = readIn();
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
c[i][j] = readIn();
// printf("%d ", c[i][j]);
}
}
solve1();
solve2();
return 0;
}
Partager