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

发表于   |  

忘了写Sol，现在自己看不懂了orz

问题描述

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

编程任务

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

数据输入

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

结果输出

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

输入文件示例 shuttle.in

2 3
10 1 2
25 2 3
5 6 7

输出文件示例 shuttle.out

1 2
1 2 3
17

Sol

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define maxn 410
#define maxm 20000
#define S 0
#define T 400
#define INF 1000000007
#define d(i) i + 150
using namespace std;

struct Edge
{
	int v, f, l, nex, w;
}ed[maxm];
int n, m, dis[maxn], e, fir[maxn];

int addedge(int u, int v, int f, int l){
	ed[++e].v = v;
	ed[e].f = f;
	ed[e].w = f;
	ed[e].l = e+l;
	ed[e].nex = fir[u];
	fir[u] = e;
}

queue <int> q;
bool bfs(){
	memset(dis, -1, sizeof dis);
	while (!q.empty()) q.pop();
	q.push(S);
	dis[S] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = fir[u]; i; i = ed[i].nex) {
			int v = ed[i].v;
			if (ed[i].f && dis[v] == -1){
				dis[v] = dis[u] + 1;
				if (v==T) return true;
				q.push(v);
			}
		}
	}
	return false;
}
int finds(int u, int maxflow = INF){
	int flow;
	if (u == T) return maxflow;
	for (int i = fir[u]; i; i = ed[i].nex){
		int v = ed[i].v;
		if (ed[i].f && dis[v] == dis[u] + 1 && (flow = finds(v, min(maxflow, ed[i].f)))  ){
			ed[i].f -= flow;
			ed[ed[i].l].f += flow;
			return flow;
		}
	}
	return 0;
}
int dinic(){
	int cnt = 0, flow;
	while (bfs()) {
			while (flow = finds(S)) {
			cnt += flow;
		}
	}
	return cnt;
}

bool bo[maxn];
void dfs(int u){
	bo[u] = true;
	for (int i = fir[u]; i; i = ed[i].nex){
		int v = ed[i].v;
		if (ed[i].f && !bo[v]) {
			bo[v] = true;
			dfs(v);
		}
	}
}

void getNum(int u, char s[]){
	int x = 0, i = 0;
	for (i = 0; i <= strlen(s); i++){
		if (s[i] >= '0' && s[i] <='9') x = x * 10 + s[i] -'0';
		else {
			addedge(S, u, x, 1);
			addedge(u, S, 0, -1);
			x = 0;
			break;
		}
	}
	for (i++; i <= strlen(s); i++){
		if (s[i] >= '0' && s[i] <='9') x = x * 10 + s[i] -'0';
		else {
			addedge(u, d(x), INF, 1);
			addedge(d(x), u, 0, -1);
			x = 0;
		}
	}
}

int ans1[maxn], ans2[maxn], a1 = 0, a2 = 0, ans = 0;
int main(){
freopen(""shuttle.in"", ""r"", stdin);
freopen(""shuttle.out"", ""w"", stdout);
	scanf(""%d%d\n"", &m, &n);
	char str[1001];
	for (int i = 1; i <= m; i++){
		gets(str);
		getNum(i, str);
	}
	for (int i = 1; i <= n; i++){
		int c;
		scanf(""%d"", &c);
		addedge(d(i), T, c, 1);
		addedge(T, d(i), 0, -1);
	}
	dinic();
	dfs(S);

	for (int i = fir[S]; i; i = ed[i].nex){
		int v = ed[i].v;
		if (bo[v]) { ans += ed[i].w; ans1[++a1] = v; }
	}

	for (int i = fir[T]; i; i = ed[i].nex){
		int v = ed[i].v;
		if (bo[v]) {ans -= ed[ed[i].l].w; ans2[++a2] = v; }
	}
	sort(ans1+1, ans1+a1+1);
	sort(ans2+1, ans2+a2+1);
	for (int i = 1; i <= a1; i++) printf(""%d "", ans1[i]);
	printf(""\n"");
	for (int i = 1; i <= a2; i++) printf(""%d "", ans2[i] - 150);
	printf(""\n""); 
	printf(""%d\n"", ans);
}