「LOJ6001」「网络流 24 题」太空飞行计划

Description

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1,E2,,Em}E = \{ E_1, E_2, \cdots, E_m \},和进行这些实验需要使用的全部仪器的集合I={I1,I2,,In}I = \{ I_1, I_2, \cdots, I_n \}。实验EjE_j需要用到的仪器是II的子集RjIR_j \subseteq I

配置仪器IkI_k的费用为ckc_k美元。实验EjE_j的赞助商已同意为该实验结果支付pjp_j美元。W 教授的任务是找出一个有效算法,确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。

对于给定的实验和仪器配置情况,编程找出净收益最大的试验计划。

Input

11行有22个正整数mmnn
mm是实验数,nn是仪器数。接下来的mm行,每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用;接着是该实验需要用到的若干仪器的编号。最后一行的nn个数是配置每个仪器的费用。

Output

11行是实验编号,第22行是仪器编号,最后一行是净收益。

请不要输出行末空格以免被判答案错误!

Sample Input

1
2
3
4
2 3
10 1 2
25 2 3
5 6 7

Sample Output

1
2
3
1 2
1 2 3
17

HINT

1n,m501 \leq n, m \leq 50

Solution

正点和负点连容量为infinf的边。
源点向正点连容量为viv_i
负点向汇点连容量为vi-v_i
最后答案==正点权值之和-最小割
考虑最小割的意义,要么割源点到正点的边,意味着这个实验不要;要么割负点到汇点的边,意味着它要购买且它对应的实验都会用到。
盗一张图:

输出方案是方便的,输入就用一个标记找换行符终止就行了。

这就是为什么用最后一次分层图是否有did_i是否非00来判断是否是答案。
如果能走到的,那么他们就全都可以用。
因为不能到达的都是割,已经删掉了。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
bool fg;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();} if(ch == '\r' || ch == '\n') fg = 1; return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 70*2, M = 70*70*2*3;
int m, n;
int s, t;
struct Edge {
int u ,v, nxt, f;
}e[M * 2];
int head[N], en = 1;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
const int inf = 1e9;
int d[N];
bool bfs() {
queue<int>q;
q.push(s);
for(int i = 1; i <= t; ++i) d[i] = 0;
d[s] = 1;
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f){
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if(x == t) return flow;
int k, rest = flow;
for(int i = head[x]; i && rest; i = e[i].nxt) if(d[e[i].v] == d[x] + 1) {
int y = e[i].v;
k = dinic(y, min(rest, e[i].f));
e[i ^ 1].f += k;
e[i].f -= k;
rest -= k;
}
return flow - rest;
}
vector<int>t1,t2;
int main() {
m = read(), n = read();
s = n + m + 1;
t = n + m + 2;
int sum = 0;
for(int i = 1; i <= m; ++i) {
int x = read();
sum += x;
addedge(s, i, x);
fg = 0;
while(!fg) {
int y = read();
addedge(i, y + m, inf);
}
}
for(int i = 1; i <= n; ++i)
addedge(i + m, t, read());
int res = 0, y;
while(bfs()) while(y = dinic(s, inf)) res += y;
for(int i = 1; i <= m; ++i)
if(d[i])
t1.pb(i);
for(int i = m + 1; i <= n + m; ++i)
if(d[i])
t2.pb(i - m);
for(int i = 0; i < t1.size(); ++i) {
printf("%d", t1[i]);
if(i < t1.size() - 1) putchar(' ');
}
puts("");
for(int i = 0; i < t2.size(); ++i) {
printf("%d", t2[i]);
if(i <t2.size() - 1) putchar(' ');
}
puts("");
writeln(sum - res);
return 0;
}