[BZOJ 2245][SDOI 2011] 工作安排

题目大意

\(n\) 类产品和 \(m\) 个员工,产品的需求量是 \(c_i\) ,用一个 01 矩阵表是每个员工能做哪些产品。同时,每个员工会有一个愤怒值,愤怒值与一个员工制作的产品数有分段一次函数关系,具体地说,有 \(s_i + 1\) 段,段的分界值为 \(t_{i, j}\) 在制作第 \(t_{i, j} \sim t_{i, j + 1}\) 件物品时,每件物品会使其愤怒值增加 \(w_{i, j}\) ,保证 \(0 < w_{i, j} < w_{i, j + 1}\) ,规定 \(t_{i, 0} = 0, \; t_{i, s_i + 1} = +\infty\) 。求最小的愤怒值之和。

\(1 \leqslant m, \; n \leqslant 250\)

\(0 \leqslant s_i \leqslant 5\)

\(0 < w_{i, j}, \; t_{i, j}, \; c_i \leqslant 100,000\)

题目链接

BZOJ 2245

CodeVS 1823

题解

费用流。

从源点向每个物品连容量为其需求的边,从每个物品向能制作它的员工连容量无穷的边;对于每个员工,从员工向汇点连容量为 \(t_{i, j + 1} - t_{i, j}\) 、费用为 \(w_{i, j}\) 的边,由于 \(w_{i, j}\) 的单调递增,一定会先走一开始的边,所以是正确的。

代码

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
#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>
const int MAXN = 255;
const int MAXS = 10;
struct Edge;
struct Node {
Edge *e, *pre;
int dist, flow;
bool inq;
} N[MAXN << 1];
struct Edge {
Node *u, *v;
Edge *next, *rev;
int cap, flow, cost;
Edge(Node *u, Node *v, int cap, int cost) : u(u), v(v), cap(cap), flow(0), cost(cost), next(u->e) {}
};
void addEdge(int u, int v, int cap, int cost) {
N[u].e = new Edge(&N[u], &N[v], cap, cost);
N[v].e = new Edge(&N[v], &N[u], 0, -cost);
N[u].e->rev = N[v].e;
N[v].e->rev = N[u].e;
}
namespace EdmondsKarp {
void solve(int s, int t, int n, int &flow, long long &cost) {
flow = cost = 0;
while (true) {
for (int i = 0; i < n; i++) {
N[i].dist = INT_MAX;
N[i].flow = 0;
N[i].inq = false;
N[i].pre = NULL;
}
std::queue<Node *> q;
q.push(&N[s]);
N[s].dist = 0;
N[s].flow = INT_MAX;
while (!q.empty()) {
Node *u = q.front();
q.pop();
u->inq = false;
for (Edge *e = u->e; e; e = e->next) {
if (e->cap > e->flow && e->v->dist > u->dist + e->cost) {
e->v->dist = u->dist + e->cost;
e->v->flow = std::min(u->flow, e->cap - e->flow);
e->v->pre = e;
if (!e->v->inq) {
e->v->inq = true;
q.push(e->v);
}
}
}
}
if (N[t].dist == INT_MAX) break;
for (Edge *e = N[t].pre; e; e = e->u->pre) {
e->flow += N[t].flow;
e->rev->flow -= N[t].flow;
}
flow += N[t].flow;
cost += (long long) N[t].dist * N[t].flow;
}
}
}
int main() {
int m, n;
scanf("%d %d", &m, &n);
const int s = 0, t = n + m + 1;
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
addEdge(s, i, x, 0);
}
for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) {
int x;
scanf("%d", &x);
if (x) addEdge(j, i + n, INT_MAX, 0);
}
for (int i = 1; i <= m; i++) {
int s;
scanf("%d", &s);
static int T[MAXS];
T[0] = 0;
for (int j = 1; j <= s; j++) scanf("%d", &T[j]);
T[s + 1] = INT_MAX;
int w;
for (int j = 1; j <= s + 1; j++) {
scanf("%d", &w);
addEdge(i + n, t, T[j] - T[j - 1], w);
}
}
int flow;
long long cost;
EdmondsKarp::solve(s, t, t + 1, flow, cost);
printf("%lld\n", cost);
return 0;
}