题目背景
Translated by @chen_zhe
幻想乡是一个被博丽大结界和虚幻与现实的境界所包围起来的一个美妙的地方。这里人和其他生物，例如妖怪、妖精等核平共处。
射命丸文（Syameimaru Aya）是一只鸦天狗，拥有操纵风的能力，已经活了千岁以上，是《文文。新闻》的主编，拥有着一本叫做《文花帖》的手账，记录幻想乡各地的大新闻。她不仅是天狗中速度最快的鸦天狗，思考能力非常强，以别人的几倍的思考速度思考，也拥有幻想乡最高等级的力量。
（译者内心O.S.：远古的东方众都那么硬核科普的吗）
题目描述
（附注：文花帖8-8 西行寺幽幽子 「死蝶浮月」）
在接下来的$n$天中，射命丸文将要拍摄幻想乡的少女的照片并且从中为第$x$个少女拍摄GxGxGx张照片刊登在《文文。新闻》上。在第$k$天的时候文文有$C_k$个取材对象，且对于每个取材对象拍的照片必须在闭区间$[L{ki},R{k_i}]$中。如果过少，文文就搞不出大新文；如果过多，就会有少女很安格瑞。
除此之外，因为拍照设备的原因，对于第$i$天，每天的拍照数量不能超过$D_i$张。在满足这些限定的条件下，文文希望拍到的照片尽可能地多。
由于文文需要去取材，因此她把这个任务交给了你，让你帮她去解决。
输入格式
本题不定组数据，确保数据组数不超过$10$
第一行输入两个整数$n$和$m$，分别表示有$n$天，有$m$位少女。其中$n \leq 365,m \leq 1000$
接下来一行，有$m$个数字$G_1 \cdots G_m$，对于每一个$G_x$，都满足$G_x \in [0,10^5]$。
再接下来$n$段，每一段的第一行有两个整数$C,D(1 \leq C \leq 300, 0 \leq D \leq 30000)$
接下来有$C$行，每一行有三个整数$T,L,R(0 \leq T < m, 0 \leq L \leq R \leq 100)$
输出格式
如果无法满足文文的需求，那么请输出-1
否则请输出在满足需求的情况下，文文最多能拍多少张照片。
注意每输出完一组数据之后，中间要空一行。
输入样例
2 3
12 12 12
3 18
0 3 9
1 3 9
2 3 9
3 18
0 3 9
1 3 9
2 3 9
输出样例
36
Solution
终于可以有一篇黑题的题解辣！至少在写题解时这题是黑的
下面进入正题：
有源汇的上下界网络最大流
这道题有一个很明显的地方告诉你要用有上下界网络流：
且对于每个取材对象拍的照片必须在闭区间$[L{k_i},R{k_i}]$中
那么怎么求有源汇的上下界网络最大流呢？
我们抛开有源汇的最大流，先搞无源汇的上下界网络可行流
关于无源汇的上下界网络可行流的证明及做法，个人讲得不太清楚，可参考这篇博客（其实就是我懒得写）
现在问题来了，如果你已经求出了可行流，那么该怎样求有源汇的网络最大流呢？
这个很简单，只需要连一条从源点到汇点容量为INF的边，然后再在残量网络跑一边最大流就可以了。具体证明见百度
最后我们就可以根据题意建边了表示读题用了20min
Code
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
| #include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 1000100
#define INF 2000000000
#define clear(x) memset(x, 0, sizeof(x));
struct Edge {
int v, nx, w;
} e[MAXN];
int min(int a, int b) {
if (a < b) return a;
else return b;
}
int head[MAXN], ecnt = 1, n, m, p, x, _l, _r;
int dep[MAXN], cur[MAXN], di[MAXN], r, k, ans, tot, _s, _t, _c, _d;
void add(int f, int t, int w) {
e[++ecnt] = (Edge){ t, head[f], w };
head[f] = ecnt;
e[++ecnt] = (Edge){ f, head[t], 0 };
head[t] = ecnt;
}
bool bfs(int s, int t) {
memset(dep, 0x7f, sizeof(dep));
for (int i = 1; i <= k; i++) {
cur[i] = head[i];
}
std::queue<int> q;
q.push(s);
dep[s] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = e[i].nx) {
int to = e[i].v;
if (dep[to] > INF && e[i].w) {
dep[to] = dep[u] + 1;
q.push(to);
}
}
}
return dep[t] < INF;
}
int dfs(int s, int t, int l) {
if (!l || s == t) return l;
int fl = 0, f;
for (int i = cur[s]; i; i = e[i].nx) {
cur[s] = i;
int to = e[i].v;
if (dep[to] == dep[s] + 1 && (f = dfs(to, t, min(l, e[i].w)))) {
fl += f;
l -= f;
e[i].w -= f;
e[i ^ 1].w += f;
if (!l) break;
}
}
return fl;
}
int Dinic(int s, int t) {
int maxf = 0;
while (bfs(s, t)) {
maxf += dfs(s, t, INF);
}
return maxf;
}
int main() {
while (scanf("%d%d", &m, &n) != EOF) {
_s = n + m + 1;
_t = _s + 1;
r = _t + 1;
k = r + 1;
clear(head);
clear(di);
ecnt = 1;
ans = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &p);
add(i, _t, INF);
di[i] -= p;
di[_t] += p;
}
for (int i = 1; i <= m; i++) {
scanf("%d%d", &_c, &_d);
add(_s, i + n, _d);
for (int j = 1; j <= _c; j++) {
scanf("%d%d%d", &x, &_l, &_r);
x++;
add(i + n, x, _r - _l);
di[i + n] -= _l;
di[x] += _l;
}
}
for (int i = 1; i <= n + m + 2; i++) {
if (di[i] > 0) {
ans += di[i];
add(r, i, di[i]);
}
else {
add(i, k, -di[i]);
}
}
add(_t, _s, INF);
tot = Dinic(r, k);
if (tot != ans) puts("-1");
else {
printf("%d\n", Dinic(_s, _t));
}
puts("");
}
return 0;
}
|
