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

最后一部分!

「网络流 24 题」负载平衡 - 19

转化为最小代价供求问题,用最小费用最大流解决。

计算出每个仓库的盈余后,可以把问题转化为供求问题。建立供求网络,把$A$集合中所有结点看做供应节点,$B$集合所有节点看做需求结点,在能一次搬运满足供需的$A_{i}$和$B_{j}$之间连接一条费用为$1$的有向边,表示搬运一个单位货物费用为$1$。另外还要在$A_{i}$与相邻的$A_{j}$之间连接边,表示货物可以暂时搬运过去,不立即满足需求,费用也为$1$。(转自 hzwer

因此可以建出如下的图:

  • 首先求出$equal = \frac{\sum_{i = 1}^{n}w[i]}{n}$的值,每一个仓库有一个$a[i]$,令$a[i] = w[i] - equal$
  • 将一个仓库拆分为两个点,分别代表这个仓库可以输出的货流量$A$集合,仓库需要的货流量$B$集合
  • 建立超级源点$s$,若$a[i] > 0$,从$s$向$A_{i}$连一条容量为$a[i]$,费用为$0$的边
  • 建立超级源点$t$,若$a[i] < 0$,从$A_{i}$向$t$连一条容量为$-a[i]$,费用为$0$的边
  • $A$集合中的点$A_{i}$向其相邻的点$B_{i + 1},B_{i - 1},A_{i - 1}, A_{i + 1}$($0 \leq i < n$)连一条容量为$\infty$,费用为$1$的边
  • 最小费用最大流,最小费用流值就是最少搬运量

「网络流 24 题」深海机器人问题 - 20

多出发点和目的地的网络运输问题

由于“多个深海机器人可以在同一时间占据同一位置”,所以不需限制点的流量,不用拆点。而且,每条边的价值只能计算一次,容量限制要设为$1,$同时还将要连接上容量不限,费用为0的重边。

  • 把网格中每个位置抽象成网络中一个结点
  • 建立超级源点$s$,从点$s$到每个出发点$i$连接一条容量为该点出发的机器人数量,费用为$0$的边
  • 建立超级源点$t$,从每个目标点$i$到$t$连一条容量为可以到达该点的机器人数量,费用为$0$的边
  • 对于每个顶点$i$,若$j$为$i$东边或南边相邻的一个结点,从结点$i$向结点$j$连一条容量为 $1$,费用为该边价值的边
  • 对于每个顶点 $i$,若 $j$ 为 $i$ 东边或南边相邻的一个结点,从结点$i$向结点$j$一条容量为$\infty$,费用为$0$的边
  • 最大费用最大流,答案为采集到的生物标本的最高总价值

「网络流 24 题」最长 k 可重区间集问题 - 21

这个问题可以看做是求$k$条权之和最大的不相交路径,每条路径为一些不相交的区间序列。由于是最大费用流,两条路径之间一定有一些区间相交,可以看做是相交部分重复了$2$次,而$k$条路经就是最多重复了$k$次。最简单的想法就是把区间排序后,不相交的区间之间连接一条边,由于每个区间只能用一次,所以要拆点,点内限制流量。如果我们改变一下思路,把端点作为网络中的顶点,区间恰恰是特定一些端点之间的边,这样建模的复杂度更小。转自 hzwer

建模方法如下:

  • 离散化所有区间的端点,把每个端点看做一个顶点,建立超级源点$s$和超级汇点$t$
  • 从$s$到顶点$1$(最左边顶点)连接一条容量为$k$,费用为$0$的边
  • 从顶点$2n$(最右边顶点)到$t$连接一条容量为$k$,费用为$0$的边
  • 从顶点$i$到顶点$i+1(i+1 \leq 2n)$,连接一条容量为$\infty$,费用为$0$的边
  • 对于每个区间$[a,b]$,从$a$对应的顶点$i$到$b$对应的顶点$j$连接一条容量为$1$,费用为区间长度的有向边。
  • 求最大费用最大流,最大费用流值就是最长k可重区间集的长度。

「网络流 24 题」最长 k 可重线段集问题 - 22

依然是最大权不相交路径转化成为最小费用最大流问题。
建图方法同 “ 最长 k 可重区间集问题 - 21 “,这里不再赘述了
由于$COGS$上的数据有问题,所以这道题目无法评测QAQ

「网络流 24 题」火星探险问题 - 23

在$\text{COGS}$好像没有找到,有哪位大佬可以告诉我在哪里可以交这道题目吗QAQ

「网络流 24 题」骑士共存问题 - 24

最大独立集问题
同 “ 「网络流 24 题」方格取数 - 9 “ ,首先进行黑白交替染色,显然棋盘变成了一个二分图。然后对于没有障碍物的地方向骑士可以到达的地方连边(连双向边),然后跑一遍网络流,最后答案等于点数减去最大匹配数。

代码

「网络流 24 题」负载平衡 - 19

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
//  Created by ZJYelizaveta on Monday, August 21, 2017 AM10:41:54 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 a[MAX_N], b[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;

int main()
{
n = readIn();
int sum = 0, equal = 0;
for (int i = 1; i <= n; ++i) a[i] = readIn(), sum += a[i];
equal = sum / n;
for (int i = 1; i <= n; ++i) b[i] = a[i] - equal;

int s = 0, t = 2 * n + 1;
for (int i = 1; i <= n; ++i) if (b[i] > 0) addEdge(s, i, b[i], 0);
for (int i = 1; i <= n; ++i) if (b[i] < 0) addEdge(i + n, t, -b[i], 0);
for (int i = 1; i <= n; ++i) {
if (i != 1) {
addEdge(i, i - 1, INF, 1), addEdge(i, i - 1 + n, INF, 1);
}
if (i != n) {
addEdge(i, i + 1, INF, 1), addEdge(i, i + 1 + n, INF, 1);
}
}
addEdge(n, 1, INF, 1), addEdge(n, n + 1, INF, 1);
addEdge(1, n, INF, 1), addEdge(1, n + n, INF, 1);
pair<int, int> ans = minCostMaxFlow(s, t);
printf("%d\n", ans.second);
return 0;
}

「网络流 24 题」深海机器人问题 - 20

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月24日 星期四 22时35分18秒
// 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 MAXNODE = 1000 + 3;
const int INF = 0x3f3f3f3f;
int a, b;
int p, q;

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;


int main()
{
freopen("shinkai.in", "r", stdin);
freopen("shinkai.out", "w", stdout);
a = readIn(), b = readIn();
p = readIn() + 1, q = readIn() + 1;

int s = 0, t = p * q + 1;
for (int i = 0; i < p; ++i) {
for (int j = 1; j < q; ++j) {
int c = readIn();
int u = i * q + j, v = u + 1;
addEdge(u, v, 1, -c); addEdge(u, v, INF, 0);
}
}
for (int j = 1; j <= q; ++j) {
for (int i = 0; i <= p - 2; ++i) {
int c = readIn();
int u = i * q + j, v = u + q;
addEdge(u, v, 1, -c); addEdge(u, v, INF, 0);
}
}
for (int i = 1; i <= a; ++i) {
int c = readIn(), x = readIn(), y = readIn();
addEdge(s, x * q + y + 1, c, 0);
}
for (int i = 1; i <= b; ++i) {
int c = readIn(), x = readIn(), y = readIn();
addEdge(x * q + y + 1, t, c, 0);
}
pair<int, int> ans = minCostMaxFlow(s, t);
printf("%d\n", -ans.second);
return 0;
}

「网络流 24 题」最长 k 可重区间集问题 - 21

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
//  Created by ZJYelizaveta on Monday, August 21, 2017 PM01:53:40 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 = 500 + 3;
const int MAXNODE = 1000 + 3;
const int INF = 0x3f3f3f3f;
int n, k;
int l[MAX_N], r[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 prevE[MAXNODE], prevV[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(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;
prevV[e.to] = u; prevE[e.to] = i;
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;

vector<int> vec;
map<int, int> mp;
int main()
{
n = readIn(), k = readIn();
for (int i = 1; i <= n; ++i) {
l[i] = readIn(), r[i] = readIn();
if (l[i] > r[i]) swap(l[i], r[i]);
vec.push_back(l[i]), vec.push_back(r[i]);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());//
int m = vec.size();

int s = m, t = m + 1;
addEdge(s, 0, k, 0), addEdge(m - 1, t, k, 0);
for (int i = 0; i < m; ++i) {
mp[vec[i]] = i;
if (i + 1 < m) addEdge(i, i + 1, INF, 0);
}
for (int i = 1; i <= n; ++i) addEdge(mp[l[i]], mp[r[i]], 1, l[i] - r[i]);
pair<int, int> ans = minCostMaxFlow(s, t);
printf("%d\n", -ans.second);
return 0;
}

「网络流 24 题」最长 k 可重线段集问题 - 22

「网络流 24 题」火星探险问题 - 23

「网络流 24 题」骑士共存问题 - 24

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骞?8鏈?5鏃 鏄熸湡浜 08鏃?0鍒?8绉
// 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 = 200 + 3;
const int MAXNODE = 400000 + 3;
const int INF = 0x3f3f3f3f;
const int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
int n, m;
int a[MAX_N][MAX_N];
int s, t, 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[MAXNODE];
int iter[MAXNODE], level[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() {
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;

inline int ID(int x, int y) {
return (y - 1) * n + x;
}

int main()
{
freopen("knight.in", "r", stdin);
freopen("knight.out", "w", stdout);

n = readIn(), m = readIn();
s = 0, t = n * n + 1, ans = n * n;
memset(a, 0, sizeof a);
for (int i = 1; i <= m; ++i) {
a[readIn()][readIn()] = 1;
--ans;
}
for (int j = 1; j <= n; ++j) for (int i = 1; i <= n; ++i) if (!a[i][j]) {
if ((i + j) & 1) {
addEdge(s, ID(i,j), 1);
for (int k = 0; k <= 7; ++k) {
int x = i + dx[k], y = j + dy[k];
if (1 <= x && x <= n && 1 <= y && y <= n && !a[x][y]) addEdge(ID(i, j), ID(x, y), INF);
}
}
else addEdge(ID(i,j), t, 1);
}
ans -= maxFlow(s, t);
printf("%d\n", ans);
return 0;
}
Partager