【线性规划与网络流24题 2】太空飞行计划

Description

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

由于本OJ无Special Judge ，所以只需要输出最多能得到的净获利。

Input

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

Output

/*
程序运行结束时，将最佳实验方案输出。
第 1 行是实验编号；第 2行是仪器编号；
最后一行是净收益。
*/
一行，包含一个整数，表示最大净收益

Sample Input

Sample Output

/*
1 2
1 2 3
*/
17

这个题是一个很经典的模型：最大权闭合图（可以参见论文：最小割模型在信息学竞赛中的应用）

闭合图的性质反映的是事件的必要条件：A发生，那么A的所有前提要发生

在本题中，做实验是有收益的，但是，实验必须要有相关设备才能完成，而购买相关设备则是有花费的

这就构成了事件的必要条件：要想做实验，先把某个实验所必须的设备购买好

把每个实验看作二分图X集合中的顶点，每个设备看作二分图Y集合中的顶点，增加源S和汇T。
1、从S向每个Xi连接一条容量为该点收入的有向边。
2、从Yi向T连接一条容量为该点支出的有向边。
3、如果一个实验i需要设备j，连接一条从Xi到Yj容量为无穷大的有向边。

所有实验的收入只和Total，求网络最大流Maxflow，最大收益就是Total-Maxflow

补充：

当题目中有点权的时候，常见的有三种做法

A：建立源点S，将点权化为S到该点u的边权

B：建立汇点T，将点权化为该点u到T的边权

C：拆点，将点权化为u1-u2的边权（这种时候，一般是卡容量或者卡流量的题了，比如POJ 3281，需要对牛进行拆点，来限制每头牛）

如何求匹配的方案？

如果使用的是dinic的模板，那么：dep【x】不为初始化的值，那么就表明这个点是取过的

代码如下：

//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;

const int maxn=1100;
const int maxm=12010;
const int INF=999999;

struct Edge{
	int to,nxt,cap,flow;
}edge[maxm];
int tol,Head[maxn];

void init(){
	memset(Head,-1,sizeof(Head));
	tol=2;
}

void addedge(int u,int v,int w,int rw=0){
	edge[tol].to=v;
	edge[tol].cap=w;
	edge[tol].flow=0;
	edge[tol].nxt=Head[u];
	Head[u]=tol++;
	
	edge[tol].to=u;
	edge[tol].cap=rw;
	edge[tol].flow=0;
	edge[tol].nxt=Head[v];
	Head[v]=tol++;
}

int Q[maxn],dep[maxn],cur[maxn],sta[maxn];

bool bfs(int s,int t,int n){
	int front=0,tail=0;
	memset(dep,-1,sizeof(dep[0])*(n+1));
	dep[s]=0;
	Q[tail++]=s;
	while(front<tail){
		int u=Q[front++];
		for(int i=Head[u];i!=-1;i=edge[i].nxt){
			int v=edge[i].to;
			if (edge[i].cap>edge[i].flow&&dep[v]==-1){
				dep[v]=dep[u]+1;
				if (v==t) return true;
				Q[tail++]=v;
			}
		}
	}
	return false;
}

int dinic(int s,int t,int n){
	int maxflow=0;
	while(bfs(s,t,n)){
		for(int i=0;i<n;i++) cur[i]=Head[i];
		int u=s,tail=0;
		while(cur[s]!=-1){
			if (u==t) {
				int tp=INF;
				for(int i=tail-1;i>=0;i--) 
					tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
				maxflow+=tp;
				for(int i=tail-1;i>=0;i--){
					edge[sta[i]].flow+=tp;
					edge[sta[i]^1].flow-=tp;
					if (edge[sta[i]].cap-edge[sta[i]].flow==0) tail=i;
				}
				u=edge[sta[tail]^1].to;
			}
			else if (cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){
				sta[tail++]=cur[u];
				u=edge[cur[u]].to;
			}
			else{
				while(u!=s&&cur[u]==-1) u=edge[sta[--tail]^1].to;
				cur[u]=edge[cur[u]].nxt;
			}
		}
	}
	return maxflow;
}

int main(){
	//freopen("input.txt","r",stdin);
	//freopen("shuttle.in","r",stdin);
	//freopen("shuttle.out","w",stdout);
	init();
	int n,m;
	scanf("%d%d",&n,&m);
	int s=0,t=n+m+1,tot=n+m+2,x;
	int sumpoint=0,mincut=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		//maze[s][i]=x;
		addedge(s,i,x);
		sumpoint+=x;
		char ch=getchar();
		while(ch!='\n'){
			scanf("%d",&x);
			//maze[i][x+n]=INF;
			addedge(i,x+n,INF);
			ch=getchar();
		}
	}
	for(int j=1;j<=m;j++){
		scanf("%d",&x);
		//maze[j+n][t]=x;
		addedge(j+n,t,x);
	}
	mincut=dinic(s,t,tot);
	/*
	for(int i=1;i<=n;i++)
		if (dep[i]!=-1) printf("%d ",i);
	printf("\n");
	for(int i=1;i<=m;i++)
		if (dep[i+n]!=-1) printf("%d ",i);
	printf("\n");
	*/
	printf("%d\n",sumpoint-mincut);
	return 0;
}