HDU 5644 King's Pilots(网络流)

题目大意

国王阅兵式会持续 $n$ 天,每天都有一场飞机表演,第 $i$ 天的飞行表演需要个 $p_i$ 飞行员。飞行员只愿意无偿工作一天。于是这个国家出台了 $m$ 个休假政策,当某个飞行员工作后,如果支付他 $S_j$ 的酬劳,他会在上次工作 $T_j$ 天后重新回来工作。

开始有 $k$ 名飞行员,当然还可以招募新的飞行员,但是,招募需要 $P$ 天的时间,并且招募来的每个飞行员需要支付 $Q$ 作为酬劳。(也就意味着到第 $P$ 天你才可能用到新招募来的飞行员)

现要求通过合理安排,保证每天的飞行员数量足够(若不能,输出“No solution”),并且让总费用最低。输出总费用。
$(m \leq 5, 其他所有数据均在区间[0, 200]内)$


解题思路

最小费用最大流

此题难就难在建图

假设先不考虑休假政策:

  • 从源点 $s$ 向每个飞行员连一条容量为 $1$,费用为 $0$ 的边
  • 从每个飞行员向每一天连一条容量为 $1$,费用为 $0$ 的边
  • 从每一天向汇点 $t$ 连一条容量为 $p_i$,费用为 $0$ 的边

上面的建图过程中可以发现,每个飞行员都是相同的,所以可以直接把所有飞行员缩为一个点,甚至直接省略掉。
这里可以有两种建图方式:

  1. 由源点 $s$ 直接向第一天连一条容量为 $k$,费用为 $0$ 的边,从第 $i$ 天向第 $i+1$ 天连一条容量为 $INF$,费用为 $0$ 的边。
  2. 所有飞行员缩成一个点,源点 $s$ 向该点连一条容量为 $k$,费用为 $0$ 的边,该点向每一天连一条容量为 $k$,费用为 $0$ 的边。

本题采用第一种。

招募新的飞行员:

  • 从源点 $s$ 向第 $P$ 天连一条容量为 $INF$,费用为 $0$ 的边(假设采用第一种建图方式)

考虑休假政策:

一开始考虑时是从 $k$ 名飞行员入手,想着如何让其“增加休假属性”。可是一方面又要让其每名飞行员一开始只选择一个点(无偿),一方面又要让其之后能够选择其他点(有偿),两方面难以同时存在。陷入了误区。

其实可以这样考虑,相当于我们有 $k$ 名飞行员是无偿的,其他都是有偿的。也就是把每一天工作过的飞行员当成新的飞行员向之后进行跳转。此时需要把每一天拆成两个点 $x$, $y$:

  • 从 $x_i$ 向 $y_{i+T}$ 连一条容量为 $INF$,费用为 $S$ 的边
  • 从源点 $s$ 向 $x_i$ 连一条容量为 $p_i$,费用为 $0$ 的边
  • 从 $y_i$ 向汇点 $t$ 连一条容量为 $p_i$,费用为 $0$ 的边

可能有些人会疑惑若这一天的飞行员数量不足 $p_i$,那直接从源点向 $x_i$ 连一条容量为 $p_i$ 的边不就错了。可仔细想想,如果是这样(不足 $p_i$ ),那意味着前面的 $y_i$ 没有满流,已经属于 “No solution”了。

代码如下:

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 1e3 + 10;
const int MAXM = 1e5 + 10;
const int INF = 0x3f3f3f3f;

struct edge {
int to, cap, cost, next;
edge( int to = 0, int cap = 0, int cost = 0, int next = 0 ) : to(to), cap(cap), cost(cost), next(next) {}
} G[MAXM << 1];
int n;
int tot, head[MAXN];
int d[MAXN], pre[MAXN];
bool inque[MAXN];

void init()
{

tot = 0;
memset(head, -1, sizeof(head));
}
void add_edge(int u, int v, int cap, int cost)
{

G[tot] = edge(v, cap, cost, head[u]);
head[u] = tot++;
G[tot] = edge(u, 0, -cost, head[v]);
head[v] = tot++;
}
bool spfa(int s, int t)
{

memset(d, -1, sizeof(d));
memset(pre, -1, sizeof(pre));
memset(inque, 0, sizeof(inque));
queue<int> que;
que.push(s);
inque[s] = true;
d[s] = 0;

while( !que.empty() )
{
int u = que.front(); que.pop();
inque[u] = false;
for( int i = head[u]; ~i; i = G[i].next )
{
edge &e = G[i];
if( e.cap > 0 && (d[e.to] == -1 || d[e.to] > d[u] + e.cost) )
{
d[e.to] = d[u] + e.cost;
pre[e.to] = i;
if( !inque[e.to] )
{
que.push(e.to);
inque[e.to] = true;
}
}
}
}

return ~d[t];
}
int Min_Cost_Max_Flow(int s, int t, int &cost)
{

cost = 0;
int f = 0;
while( spfa(s, t) )
{
int Min = INF;
for( int i = pre[t]; ~i; i = pre[G[i ^ 1].to] )
{
Min = min(Min, G[i].cap);
}
for( int i = pre[t]; ~i; i = pre[G[i ^ 1].to] )
{
G[i].cap -= Min;
G[i ^ 1].cap += Min;
}
cost += d[t] * Min;
f += Min;
}
return f;

}
int main()
{

int T;
scanf("%d", &T);
while( T-- )
{
init();
int k, m, P, Q;
scanf("%d %d", &n, &k);
int s = 0, t = 2 * n + 1;
int p, sum = 0;
add_edge(s, 1, k, 0);
for( int i = 1; i <= n; ++ i )
{
scanf("%d", &p);
sum += p;
if( i < n ) add_edge(i, i + 1, INF, 0);
add_edge(i, t, p, 0);
add_edge(s, n + i, p, 0);
}
scanf("%d %d %d", &m, &P, &Q);
int x, y;
for( int i = 0; i < m; ++ i )
{
scanf("%d %d", &x, &y);
for( int j = 1; j <= n - y; ++ j )
{
add_edge(n + j, j + y, INF, x);
}
}
for( int i = P; i <= n; ++ i )
{
add_edge(s, i, INF, Q);
}
int cost;
int f = Min_Cost_Max_Flow(s, t, cost);
if( f < sum ) puts("No solution");
else printf("%d\n", cost);
}

return 0;
}
如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!