本文共 1411 字，大约阅读时间需要 4 分钟。
题目大意： 有一些实验和一些仪器，每个实验要用到一些仪器，做一个实验有收益，用一个仪器有代价，现在选择做一些实验，假如两个实验用到同一个仪器，不需要支付两次代价，问最大利益是多少。
题解参照，这篇博客只是贴个代码：
#include#include #include using namespace std;#define maxn 210#define inf 999999999int n,m,val[maxn],S,T,sum=0;struct edge{ int x,y,z,next;};edge e[maxn*maxn<<1];int first[maxn],len=1;void buildroad(int x,int y,int z){ e[++len]=(edge){ x,y,z,first[x]}; first[x]=len;}int h[maxn],q[maxn],st,ed;bool bfs(){ memset(h,0,sizeof(h)); st=ed=1;q[st]=S;h[S]=1; while(st<=ed) { int x=q[st++]; for(int i=first[x];i;i=e[i].next) if(!h[e[i].y]&&e[i].z)h[q[++ed]=e[i].y]=h[x]+1; } return h[T];}int dfs(int x,int flow){ if(x==T)return flow; int tt=0,p; for(int i=first[x];i;i=e[i].next) { int y=e[i].y; if(h[y]==h[x]+1&&e[i].z) { p=dfs(y,min(e[i].z,flow-tt));tt+=p; e[i].z-=p;e[i^1].z+=p; if(tt==flow)break; } } if(!tt)h[x]=0; return tt;}int main(){ scanf("%d %d",&n,&m);S=n+m+1;T=S+1; for(int i=1,x;i<=n;i++) { scanf("%d",&x);sum+=x; buildroad(S,i,x),buildroad(i,S,0); while(getchar()==' ')scanf("%d",&x), buildroad(i,x+n,inf),buildroad(x+n,i,0); } for(int i=1;i<=m;i++)scanf("%d",&val[i]), buildroad(i+n,T,val[i]),buildroad(T,i+n,0); int ans=0; while(bfs())ans+=dfs(S,inf); for(int i=1;i<=n;i++)if(h[i])printf("%d ",i);//输出与S相连的点 printf("\n"); for(int i=1;i<=m;i++)if(h[i+n])printf("%d ",i); printf("\n"); printf("%d\n",sum-ans);}
转载地址：http://rcnib.baihongyu.com/