洛谷2050 - [NOI2012]美食节

网络流裸题,没什么好说的。
需要注意的是,我们在给厨师拆点的时候,如果先把边都连好,时间是会炸掉的。所以我们就没“用掉”一个厨师新建一次点即可。

代码:

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
// =================================
// author: memset0
// date: 2019.01.28 17:19:06
// website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
namespace ringo {
template <class T> inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (f) x = -x;
}
template <class T> inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 50, M = 110, P = 810, Nd = 80110, Ed = 2e7 + 10;
int n, m, s, e, cnt, ans, sum, cos;
int a[N], w[N][M], at[N], id[M][P], pre[Nd], dis[Nd], vis[Nd], lst[M], bln[Nd];
int tot = 2, hed[Nd], nxt[Ed], to[Ed], val[Ed], cst[Ed];

inline void add(int u, int v, int w, int c) {
nxt[tot] = hed[u], to[tot] = v, val[tot] = w, cst[tot] = c, hed[u] = tot++;
nxt[tot] = hed[v], to[tot] = u, val[tot] = 0, cst[tot] = -c, hed[v] = tot++;
}

bool spfa() {
for (int i = 1; i <= cnt; i++) pre[i] = 0, dis[i] = 0x3f3f3f3f;
static int q[Nd], l, r, u; vis[q[l = r = 1] = s] = 1, dis[s] = 0;
while (l <= r) {
vis[u = q[(l++) % Nd]] = 0;
for (int i = hed[u], v = to[i]; i; i = nxt[i], v = to[i])
if (val[i] && dis[u] + cst[i] < dis[v]) {
dis[v] = dis[u] + cst[i], pre[v] = i;
if (!vis[v]) vis[q[(++r) % Nd] = v] = 1;
}
} return pre[e];
}

void main() {
read(n), read(m), s = ++cnt, e = ++cnt;
for (int i = 1; i <= n; i++) read(a[i]), at[i] = ++cnt, sum += a[i];
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) read(w[i][j]);
for (int i = 1; i <= n; i++) add(s, at[i], a[i], 0);
for (int i = 1; i <= m; i++) for (int j = 1; j <= sum; j++) id[i][j] = ++cnt, bln[cnt] = i;
for (int i = 1; i <= m; i++) {
add(id[i][lst[i] = 1], e, 1, 0);
for (int j = 1; j <= n; j++) add(at[j], id[i][1], 1, w[j][i]);
}
for (int t = 1; t <= sum; t++) {
spfa();
for (int i = pre[e]; i; i = pre[to[i ^ 1]])
--val[i], ++val[i ^ 1], ans += cst[i];
cos = bln[to[pre[e] ^ 1]];
add(id[cos][++lst[cos]], e, 1, 0);
for (int i = 1; i <= n; i++) add(at[i], id[cos][lst[cos]], 1, lst[cos] * w[i][cos]);
} print(ans, '\n');
}

} signed main() { return ringo::main(), 0; }
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×