链接：https://www.oj.swust.edu.cn/oj/problem/show/1737
分析：把实验和仪器都看做点，点权为盈利（仪器的盈利为负），从实验到所需仪器连一条边，求图的最大权闭合图。
最大权闭合图求法：增加源汇点s、t，对于每个点，设权重为w，若w>0，从s向该点连一条边，容量为w，若w<0，从该点向t连一条边，容量为-w，再把原有的边全部容量改为无穷大，求一下该图的最小割即为最大权，割完和s所在集合就是最大权闭合图，也就是需要做的实验和需要的仪器。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 const int maxn=1e3+5,INF=1e9; 9 int m,n; 10 struct Edge{ 11 int from,to,cap,flow; 12 Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){} 13 }; 14 struct ISAP{ 15 int n,s,t; 16 vector edges; 17 vector G[maxn]; 18 bool vis[maxn]; 19 int d[maxn]; 20 int cur[maxn]; 21 int p[maxn]; 22 int num[maxn]; 23 24 void init(int n){ 25 this->n=n; 26 edges.clear(); 27 for(int i=0;i
Q; 40 Q.push(t); 41 d[t]=0; 42 vis[t]=1; 43 while(!Q.empty()){ 44 int x=Q.front();Q.pop(); 45 for(int i=0;i
s=s;this->t=t; 75 int flow=0; 76 BFS(); 77 memset(num,0,sizeof(num)); 78 for(int i=0;i e.flow&&d[x]==d[e.to]+1){ 90 ok=1; 91 p[e.to]=G[x][i]; 92 cur[x]=i; 93 x=e.to; 94 break; 95 } 96 } 97 if(!ok){ 98 int m=n-1; 99 for(int i=0;i e.flow)m=min(m,d[e.to]);102 }103 if(--num[d[x]]==0)break;104 num[d[x]=m+1]++;105 cur[x]=0;106 if(x!=s)x=edges[p[x]].from;107 }108 }109 return flow;110 }111 }isap;112 113 int main(){114 // freopen("e:\\in.txt","r",stdin);115 scanf("%d%d",&m,&n);116 char c;117 int v,ans=0;118 isap.init(n+m+2);119 for(int i=n+1;i<=n+m;i++){120 scanf("%d",&v);121 ans+=v;122 isap.AddEdge(0,i,v);123 c=getchar();124 while(c==' '){125 scanf("%d",&v);126 c=getchar();127 isap.AddEdge(i,v,INF);128 }129 }130 for(int i=1;i<=n;i++){131 scanf("%d",&v);132 isap.AddEdge(i,n+m+1,v);133 }134 ans-=isap.Maxflow(0,n+m+1);135 isap.BFS();136 for(int i=n+1;i<=n+m;i++){137 if(!isap.vis[i]){138 printf("%d ",i-n);139 }140 }141 142 printf("\n");143 for(int i=1;i<=n;i++){144 if(!isap.vis[i]){145 printf("%d ",i);146 }147 }148 printf("\n");149 printf("%d\n",ans);150 return 0;151 }