太空飞行计划

题目描述

输入格式

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

(1<=n, m<=50)

输出格式

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

输入样例

23 

10 1 2 

25 2 3 

5 6 7

输出样例 2209.out

12 

1 2 3 

17

关于这题的吐槽：

    最坑的不是构图or输出方案，这题的输入就够人磨一阵子的了。因为在输入了同意支付这个实验的费用以后，接的是若干台仪器。若干……简直不想吐槽了，逼得只能用字符串s直接输入这一整行，然后再慢慢分解。结果单单输入就直接占了50多行的代码位置。

解题思想：

    关于这题的构图方法要感谢ywq同学，讲得挺通俗易懂。从收益上考虑。如果不做这个实验，那就得不到这笔经费，会有所损失；如果做这台实验，虽然经费的支柱，但是要买仪器，同样会损失。而我们要做的就是看割哪一条边会损失最小。

构图：

    把实验编号放在左边，与节点s连接，仪器编号放右边，与节点t连接。跑一次最小割，得出来的就是消费最大的选择。

 

    注意，图中的仪器编号已经向后移了m。

输出方案：

    最后在残余网络中，查看，哪些边被格调，即可以相连的两条边之间，v[now]是被选的（赋值为1），v[to]是不被选的，假设to是实验，那么说明不做这个实验；如果是仪器，那么说明选择这台仪器。

    那么怎么区别是实验还是仪器呢？只要看它隔开的那条边，即to是否为t，如果为，那么说明是仪器，把这台now仪器标记为不取，否则，说明是实验，那么把to实验标记为不取。

    为了更清晰地表示为什么实验是to，仪器是now，回到上面的图，复原一下会是怎么割的，割掉的说明不取会更好。

 

    看图分析就比较直观了。

代码如下：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int  maxn=205,oo=1000000000;int m,n,s,t,ans,ma[maxn],ex[maxn],v[maxn],head[maxn],c[maxn],p[maxn],cur=-1;string ss; struct space{	int to,next,va,type;}edge[maxn*maxn];void add(int from,int to,int va,int type){	cur++;	edge[cur].to=to;	edge[cur].va=va;	edge[cur].type=type;	edge[cur].next=head[from];	head[from]=cur;}void init()//此处是麻烦的输入{	cin>>m>>n;	s=0,t=m+n+1;		memset(head,-1,sizeof(head));	for(int i=1;i<=m+1;i++)	{		getline(cin,ss);//输入字符串		if(i>1)		{					int size=ss.size(),j=0;			while(ss[j]>='0'&&ss[j]<='9') 			{				p[i-1]=p[i-1]*10+(ss[j]-'0');				j++;			}//存下资助的金额			int num=0;			j++;			while(j
         
          >c[i];			for(int i=1;i<=m;i++)	{		ans=ans+p[i];		add(s,i,p[i],0);		add(i,s,0,1);	}//资助金额与s相连	for(int i=m+1;i<=m+n;i++)	{		add(i,t,c[i],0);		add(t,i,0,1);	}//仪器与t相连}int dfs(int now,int mi)//最大流（最小割）{	if(now==t) return mi;	v[now]=1;	int h=head[now];	while(h!=-1)	{		int to=edge[h].to,va=edge[h].va;		if(v[to]==0&&va!=0)		{			int k;			k=dfs(to,min(va,mi));			if(k!=0)			{				edge[h].va-=k;				if(edge[h].type==0) edge[h+1].va+=k;				else edge[h-1].va+=k;				return k;			}		}		h=edge[h].next;	}	return 0;}void check(int now)//扫一次残余网络。{	int h=head[now];	while(h!=-1)	{		int to=edge[h].to,type=edge[h].type;		if(type==0) 		{			if(v[now]==1&&v[to]==0)//查看哪些仪器或实验是不用的			{				if(to==t) ma[now-m]=1;				else ex[to]=1;			}			check(to);		}		h=edge[h].next;	} }void start()//输出{	check(0);	for(int i=1;i<=m;i++)	{		if(ex[i]!=1) cout<
          <<" "; } cout<