[网络流24题]太空飞行计划问题

Posted on | In , ,
网络流24题·2

题目

描述

W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到的仪器是I的子集RjíI。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。

输入

第1行有2 个正整数m和n。m是实验数，n是仪器数。接下来的m 行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。

输出

第1 行是实验编号；第2行是仪器编号；最后一行是净收益。

输入样例

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

输出样例

1
2
3
1 2
1 2 3
17

说明

n,m<=50

解题思路

先假设我们接受了所有的实验，得到了 $\Sigma p_i$ 钱，然后要么减去某实验的收益，表示没有进行这个实验，要么减去某仪器的费用，表示使用了该仪器。
实现方法是：将原点 $S$ 向实验连边，边权为该实验的收益（正数）；将仪器向汇点 $T$ 连边，边权是该仪器的费用（正数）；对应实验与仪器之间连边权为 INF 的边。如此，$\Sigma p_i - 最小割$ 即是答案。
解释：由最小割的定义可知，被割的边一定是满流的，因此要么是 $S\rightarrow 实验$，要么是 $仪器\rightarrow T$ 的边，根据前面叙述，这两种情况分别代表了没有进行该实验和使用了该仪器。
怎么输出方案呢？由以上分析可知，如果 $S$ 到某实验的边未满流，则做了该实验；某仪器到 $T$ 满流，则用了该仪器；所以，只要最后一次 dinic 时最后一次 bfs 后该点（实验/仪器）有层数，则使用了该点。

最后再吐槽一下 luogu 上的蜜汁输入……

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;

inline bool read(int& x){
	x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '\n')	return false;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		x = (x << 1) + (x << 3) + ch - '0';
		ch = getchar();
	}
	if(ch == '\n')	return false;
	return true;
}

const int N = 155;
const int INF = 1e9;

int n, m, S, T, p, tot;

struct Edge{
	int nxt, from, to, cap;
}edge[N*N<<1];
int head[N], edgeNum = 1;
void addEdge(int from, int to, int cap){
	edge[++edgeNum] = (Edge){head[from], from, to, cap};
	head[from] = edgeNum;
}

int lay[N];
bool bfs(){
    memset(lay, 0, sizeof lay);
    queue<int> q;
    q.push(S);
    lay[S] = 1;
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for(int i = head[cur]; i; i = edge[i].nxt){
            if(edge[i].cap <= 0)	continue;
            if(!lay[edge[i].to]){
                lay[edge[i].to] = lay[cur] + 1;
                q.push(edge[i].to);
            }
        }
    }
    return lay[T];
}
int dfs(int x, int minCap){
	if(x == T)	return minCap;
	for(int i = head[x]; i; i = edge[i].nxt){
		if(edge[i].cap <= 0 || lay[edge[i].to] != lay[x] + 1)	continue;
		int t = dfs(edge[i].to, min(minCap, edge[i].cap));
		if(t){
			edge[i].cap -= t;
			edge[i^1].cap += t;
			return t;
		}
	}
	return 0;
}
int dinic(){
	int maxFlow = 0;
	while(bfs())
		if(int flow = dfs(S, INF))
			maxFlow += flow;
	return maxFlow;
}

int main(){
	read(m), read(n);
	S = 101, T = 102;
	for(int i = 1; i <= m; i++){
		read(p);
		tot += p;
		addEdge(S, i, p);
		addEdge(i, S, 0);
		while(read(p)){
			addEdge(i, p+50, INF);
			addEdge(p+50, i, 0);
		}
		addEdge(i, p+50, INF);
		addEdge(p+50, i, 0);
	}
	for(int i = 1; i <= n; i++){
		read(p);
		addEdge(i+50, T, p);
		addEdge(T, i+50, 0);
	}
	int ans = tot - dinic();
	for(int i = 1; i <= m; i++)
		if(lay[i])
			printf("%d ", i);
	putchar(10);
	for(int i = 1; i <= n; i++)
		if(lay[i+50])
			printf("%d ", i);
	printf("\n%d\n", ans);
	return 0;
}