学步园

与SOJ 3109一样的题目，不过这题要求高些，还要输出选择方案

对于每个元件component，源点向它连一条容量为它代价的边，对于每件产品product，向汇点连一条容量为它价值的边

这样求得最小割后，如果（i,t)满流，一定为割边，它代表的产品肯定不选，如果（s,i)满流，不一定为割边，但割边若是(s,i)这种形式，它一定满流，且i代表的元件肯定要选

可以这么理解，如果(i,t)满流，则说明产品i的利润为小于等于0，没有利润了，因为制造它的元件的代价把利润抵消完了，与它相关的元件中，与源点相连的边可能满流，或者不满流，但只要有一条不满流，则这些边中没有一条会是割边，因为只要有一条不满流，在残余网络中，源点可以到达这件产品所代表的点，通过这个点又可以到达那些与它相关的且与源点相连的边满流的点（即生产它需要的元件表示的点）;反之，如果(i,t)没有满流，则它代表的产品能产生利润，且源点到生产它需要的那些元件顶点的边都满流，这些边都为割边

于是，最小割的割边中，如果与s相关，则对应的元件会被购买，如果与t相关，则该产品不会被制造

C[S,S']=Sum(i)+Sum(j)，i为被购买的元件，j为不会被制造的产品

令Total为所有产品的价值和，则Total-Sum(i)-Sum(j)=Total-C[S,S'](最小割的容量)，即为最大利润

最后输出结果时，先找出哪些产品需要被制造（它与汇点的边未满流），然后找出制造它需要的元件即可（与源点的边满流且与被制造的产品相关联）

第一次在ZOJ上做题，好多编译错误，唉。。。

代码：

#include<memory.h><br /> #include<string.h><br /> #include<stdio.h><br /> #include<iostream><br /> using namespace std;<br /> #define MAXN 400<br /> #define MAXL 400<br /> #define inf 1<<30<br /> struct node<br /> {<br /> int v,c,next;<br /> }g[MAXN*MAXN];<br /> int dis[MAXN],num[MAXN],pre[MAXN],cur[MAXN],adj[MAXN],res1[MAXN],res2[MAXN];<br /> char list[MAXL][50];<br /> int s,t,vn,e;<br /> void addEdge(int u,int v,int c)<br /> {<br /> g[e].v=v; g[e].c=c; g[e].next=adj[u]; adj[u]=e++;<br /> g[e].v=u; g[e].c=0; g[e].next=adj[v]; adj[v]=e++;<br /> }<br /> int find(char name[50])<br /> {<br /> for(int i=1;i<MAXL;i++)<br /> {<br /> if(strcmp(list[i],name)==0)<br /> return i;<br /> }<br /> return 0;<br /> }<br /> int sap()<br /> {<br /> int i,u,v,flow=0,aug=inf,flag;<br /> for(i=0;i<=vn;i++)<br /> {<br /> dis[i]=num[i]=0;<br /> cur[i]=adj[i];<br /> }<br /> num[0]=vn;<br /> pre[s]=u=s;<br /> while(dis[s]<vn)<br /> {<br /> flag=0;<br /> for(i=cur[u];i!=-1;i=g[i].next)<br /> {<br /> v=g[i].v;<br /> if(g[i].c&&dis[u]==dis[v]+1)<br /> {<br /> flag=1;<br /> pre[v]=u;<br /> cur[u]=i;<br /> aug=aug<g[i].c?aug:g[i].c;<br /> u=v;<br /> if(u==t)<br /> {<br /> flow+=aug;<br /> while(u!=s)<br /> {<br /> u=pre[u];<br /> g[cur[u]].c-=aug;<br /> g[cur[u]^1].c+=aug;<br /> }<br /> aug=inf;<br /> }<br /> break;<br /> }<br /> }<br /> if(flag)<br /> continue;<br /> if(--num[dis[u]]==0)<br /> break;<br /> for(dis[u]=vn,i=adj[u];i!=-1;i=g[i].next)<br /> {<br /> v=g[i].v;<br /> if(g[i].c&&dis[v]<dis[u])<br /> {<br /> dis[u]=dis[v];<br /> cur[u]=i;<br /> }<br /> }<br /> dis[u]++;<br /> num[dis[u]]++;<br /> u=pre[u];<br /> }<br /> return flow;<br /> }<br /> int main()<br /> {<br /> int i,j,N,order,component,cost,value,listNumber,cnt1,cnt2,sum;<br /> char name[50];<br /> scanf("%d",&N);<br /> while(N--)<br /> {<br /> memset(list,0,sizeof(list));<br /> memset(adj,-1,sizeof(adj));<br /> e=0;<br /> s=0;<br /> scanf("%d",&component);<br /> for(i=1;i<=component;i++)<br /> {<br /> scanf("%s%d",&name,&cost);<br /> strcpy(list[i],name);<br /> addEdge(s,i,cost);<br /> }<br /> scanf("%d",&order);<br /> t=component+order+1;<br /> vn=t+1;<br /> sum=0;<br /> for(i=1;i<=order;i++)<br /> {<br /> scanf("%s%d%d",&name,&value,&j);<br /> sum+=value;<br /> strcpy(list[component+i],name);<br /> addEdge(component+i,t,value);<br /> while(j--)<br /> {<br /> scanf("%s",&name);<br /> listNumber=find(name);<br /> addEdge(listNumber,component+i,inf);<br /> }<br /> }<br /> printf("%d/n",sum-sap());<br /> cnt1=cnt2=0;<br /> for(i=component+1;i<=component+order;i++)<br /> {<br /> for(j=adj[i];j!=-1;j=g[j].next)<br /> {<br /> if(g[j].v==t)<br /> {<br /> if(g[j].c)<br /> res1[cnt1++]=i;//保存需要制造的产品<br /> break;<br /> }<br /> }<br /> }<br /> for(i=0;i<cnt1;i++)<br /> {<br /> for(j=adj[res1[i]];j!=-1;j=g[j].next)<br /> {<br /> if(g[j].v<=component)<br /> res2[cnt2++]=g[j].v;//保存制造产品需要的元件<br /> }<br /> }<br /> printf("%d/n",cnt1);<br /> for(i=0;i<cnt1;i++)<br /> printf("%s/n",list[res1[i]]);<br /> printf("%d/n",cnt2);<br /> for(i=0;i<cnt2;i++)<br /> printf("%s/n",list[res2[i]]);<br /> printf("/n");<br /> }<br /> return 0;<br /> }