太空飞行计划

题目描述

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行是仪器编号；最后一行是净收益。

输入输出样例

输入
2 3
10 1 2
25 2 3
5 6 7

输出
1 2
1 2 3
17

题目链接：洛谷 P2762

应该不难看出是一个最大权闭合子图的问题。于是我们建立两个点，一个超级源点S，一个超级汇点T。

下面给出最大权闭合子图的一般做法：

S连正权点，权值为获得的价值
负权连T，权值为花费
正权点连接负权点，权值为INF
最后跑一遍最小割

按照上面的做法，我们可以：

让S与实验连边，权值为收入；

支出（也就是仪器）与T连边，权值为费用；

因为是闭合子图，所以我们让实验与仪器连边，权值为 INF。

这样跑一遍最小割，让总收入减去最小割就是答案。

求最小割，我用的是dinic多路增广和炸点优化。

就这样愉快地AC了！！！

我真的服了，一直提醒我非原创，我说你馬呢？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
所以下面的不用管。QWQ

这个CSDN是真的！！！！！！！！！！！！！！！！！(ZZ)

圆周率500位
3.14159 26535 89793 23846 26433
83279 50288 41971 69399 37510
58209 74944 59230 78164 06286
20899 86280 34825 34211 70679
82148 08651 32823 06647 09384
46095 50582 23172 53594 08128
48111 74502 84102 70193 85211
05559 64462 29489 54930 38196
44288 10975 66593 34461 28475
64823 37867 83165 27120 19091
45648 56692 34603 48610 45432
66482 13393 60726 02491 41273
72458 70066 06315 58817 48815
20920 96282 92540 91715 36436
78925 90360 01133 05305 48820
46652 13841 46951 94151 16094
33057 27036 57595 91953 09218
61173 81932 61179 31051 18548
07446 23799 62749 56735 18857
52724 89122 79381 83011 94912

圆周率501-1000位
98336 73362 44065 66430 86021
39494 63952 24737 19070 21798
60943 70277 05392 17176 29317
67523 84674 81846 76694 05132
00056 81271 45263 56082 77857
71342 75778 96091 73637 17872
14684 40901 22495 34301 46549
58537 10507 92279 68925 89235
42019 95611 21290 21960 86403
44181 59813 62977 47713 09960
51870 72113 49999 99837 29780
49951 05973 17328 16096 31859
50244 59455 34690 83026 42522
30825 33446 85035 26193 11881
71010 00313 78387 52886 58753
32083 81420 61717 76691 47303
59825 34904 28755 46873 11595
62863 88235 37875 93751 95778
18577 80532 17122 68066 13001
92787 66111 95909 21642 01989

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=21000;
const int inf=0x3f3f3f3f;
int m,n,res,s,t,val,h[N];
int head[N],nex[N],w[N],to[N],tot=1;
inline void ade(int a,int b,int c){
	to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c){
	ade(a,b,c);	ade(b,a,0);
}
int bfs(){
	memset(h,0,sizeof h);	queue<int> q;	q.push(s);	h[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(w[i]&&!h[to[i]]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f;
	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(w[i]&&h[to[i]]==h[x]+1){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi;	w[i^1]+=mi;	f-=mi;	fl+=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,inf);
	return res;
}
signed main(){
	cin>>m>>n;	s=0; t=n+m+1;	
	for(int i=1;i<=m;i++){
		int a; char op;	cin>>a;	add(s,i,a);	res+=a;
		while(scanf("%lld%c",&a,&op)){
			add(i,a+m,inf);
			if(op=='\n'||op=='\r')	break;
		}
	}
	for(int i=1;i<=n;i++)	cin>>val,add(i+m,t,val);
	int din=dinic();
	for(int i=1;i<=m;i++)	if(h[i])	cout<<i<<' ';puts("");
	for(int i=1;i<=n;i++)	if(h[i+m])	cout<<i<<' ';puts("");
	cout<<res-din<<endl;
	return 0;
}