欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门
题意概括
有m个实验，对应有一定的收入。有n个实验仪器，每个实验仪器的购买需要一定的花费。
对于这m个实验，每个实验分别需要使用一些实验器材（当然不是一次性的）。
问最大收入为多少。
题解
网络流解析
作为网络流24题的第二题，博主大蒟蒻就思索而且被坑了很久。
本题的构图模型：
建立两个虚点，分别为源点和汇点S和T。
然后对于每个实验，连接S和它，容量为它的收入。
对于每个实验的每个需要的仪器，连接它们，容量为无穷大。
对于每一个仪器，连接它和汇点，容量为这个仪器的花费。
然后问题就被转化成了一个最小割问题。
我们求最小割，用最大流。
SAP跑一发就可以了。
详见代码
我当时被卡很久，就是因为读入的时候循环变量重名了……
代码
#include <cstring> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cmath> using namespace std; const int N=150+5,M=N*N,Inf=1<<25; int n,m; struct Edge{ int x,y,cap,flow,nxt; }; struct Gragh{ int cnt,fst[N],dist[N],s,t,num[N],cur[N],p[N],q[N],head,tail; Edge e[M]; void set(int S,int T){ s=S,t=T,cnt=1; memset(fst,0,sizeof fst),memset(e,0,sizeof e); } void add(int a,int b,int c){ e[++cnt].x=a,e[cnt].y=b,e[cnt].cap=c,e[cnt].flow=0; e[cnt].nxt=fst[a],fst[a]=cnt; e[++cnt].x=b,e[cnt].y=a,e[cnt].cap=0,e[cnt].flow=0; e[cnt].nxt=fst[b],fst[b]=cnt; } void re_bfs(){ memset(dist,-1,sizeof dist); head=tail=0,dist[t]=0,q[++tail]=t; while (head<tail) for (int x=q[++head],i=fst[x];i;i=e[i].nxt) if (e[i].cap==0&&dist[e[i].y]==-1) dist[q[++tail]=e[i].y]=dist[x]+1; for (int i=1;i<=n;i++) if (dist[i]==-1) dist[i]=n; } int Augment(int &point){ int ex_Flow=Inf; for (int i=t;i!=s;i=e[p[i]].x) if (e[p[i]].cap-e[p[i]].flow<ex_Flow) ex_Flow=e[p[i]].cap-e[p[i]].flow,point=e[p[i]].x; for (int i=t;i!=s;i=e[p[i]].x) e[p[i]].flow+=ex_Flow,e[p[i]^1].flow-=ex_Flow; return ex_Flow; } int SAP(){ int x=s,y,MaxFlow=0; memset(num,0,sizeof num); for (int i=1;i<=n;i++) cur[i]=fst[i],num[dist[i]]++; while (dist[s]<n){ if (x==t){ MaxFlow+=Augment(x); continue; } bool found=0; for (int i=cur[x];i!=0&&!found;i=e[i].nxt) if (dist[e[i].y]+1==dist[x]&&e[i].cap>e[i].flow) p[e[i].y]=cur[x]=i,x=e[i].y,found=1; if (found) continue; int d=n+1; for (int i=fst[x];i;i=e[i].nxt) if (e[i].cap>e[i].flow) d=min(d,dist[e[i].y]+1); if (!(--num[dist[x]])) return MaxFlow; num[dist[x]=d]++,cur[x]=fst[x]; if (x!=s) x=e[p[x]].x; } return MaxFlow; } }g; int a,b,v; bool vis[N]; char ch[500]; bool isd(char ch){ return '0'<=ch&&ch<='9'; } void dfs(int x){ vis[x]=1; for (int i=g.fst[x];i;i=g.e[i].nxt) if (!vis[g.e[i].y]&&g.e[i].cap>g.e[i].flow) dfs(g.e[i].y); } int main(){ scanf("%d%d",&a,&b); n=a+b+2; g.set(n-1,n); int sum=0; for (int ii=1;ii<=a;ii++){ scanf("%d",&v); sum+=v; g.add(g.s,ii,v); gets(ch); int len=strlen(ch); for (int i=0;i<len;){ while (i<len&&!isd(ch[i])) i++; if (i>=len) break; v=0; while (i<len&&isd(ch[i])) v=v*10+ch[i]-48,i++; g.add(ii,a+v,Inf); } } for (int i=1,v;i<=b;i++){ scanf("%d",&v); g.add(i+a,g.t,v); } g.re_bfs(); int ans=g.SAP(); memset(vis,0,sizeof vis); dfs(g.s); for (int i=1;i<=a;i++) if (vis[i]) printf("%d ",i); puts(""); for (int i=1;i<=b;i++) if (vis[i+a]) printf("%d ",i); printf(" %d",sum-ans); return 0; }