https://blog.csdn.net/bjfu170203101/article/details/108955233
解法总结见我上一篇BLOG。
这里只讲一下关于最小割打印。
首先最大流只是值等于最小割，最大流选的边不一定等于最小割的边。
割是把网络分断的一个边集。
我们只需要在残留网络中S开始遍历，可达的点计为标记点(即d[i]>0的点)
若一条边 x,y满足：d[x]>0,d[y]==0 则该边属于最小割边集。
另外：其实这个模型也可以感性理解一下:
最小割一定不会选择中间的边(中间边权为无穷大)
而选择左边的边后，其边连的点表示实验编号，显然其连得器材没必要选择。(最后用实验钱数减去最小割，如果最小割里有实验，则说明这个实验不选)
而选择右边的边：其边连接汇点与实验器材，选择这条边说明选择这个实验器材。
最后对于每个实验要么做这个实验：相当于最小割中选其需要的实验器材的边。
要么不做这个实验：相当于最小割中选择其实验对应的边。
显然对于每个实验，要么选左边的边，要么选右边的边，最终选择一定是一个割。而最优选择刚好是最小割！！!
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int M = 50000+7; const int N = 400+7; struct Dinic{ //N个点，M条边 //add建双向边，然后D.gao ,最后输出maxflow #define inf 0x3f3f3f3f ll maxflow;int s,t,n; int v[N],pre[N],d[N],now[N]; ll incf[N]; int head[N],cnt=1; struct EDGE{int to,nxt;ll w;}ee[M*2]; inline void AD(int x,int y,ll w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;} inline void add(int x,int y,ll w){AD(x,y,w);AD(y,x,0);} inline bool bfs()//在残量网络上构造分层图 { memset(d,0,sizeof(d)); queue<int>q; q.push(s);d[s]=1; while(q.size()) { int x=q.front();q.pop(); for(int i=head[x];i;i=ee[i].nxt) { int y=ee[i].to;ll w=ee[i].w; if(w&&!d[y]) { q.push(y); d[y]=d[x]+1; if(y==t)return 1; } } } return false; } inline int dinic(int x,int flow) { if(x==t)return flow; ll rest = flow,k; for(int i=now[x];i&&rest;i=ee[i].nxt) { int y=ee[i].to;ll w=ee[i].w; now[x]=i; if(w&&d[y]==d[x]+1) { k=dinic(y,min(rest,w)); if(!k)d[y]=0;//剪枝，去掉增广完毕的点 ee[i].w-=k; ee[i^1].w+=k; rest-=k; } } return flow - rest; } inline void gao() { int flow=0; while(bfs()) { for(int i=0;i<=n;i++)now[i]=head[i]; while(flow=dinic(s,inf))maxflow+=flow; } } inline void init(int nn,int S,int T) { cnt=1;maxflow=0; for(int i=0;i<=n;i++)head[i]=0; s=S,t=T,n=nn; } }D; //求解二分图匹配问题时的复杂度是：m*sqrt(n)的 struct node{ int x,id; }lp[M],rp[M]; int main() { int n,m,s,t; scanf("%d%d",&n,&m); int N = n+m+2; s=n+m+1,t=n+m+2; D.init(N,s,t);//初始化节点个数，起点，终点 int sm=0,a,b; for(int i=1;i<=n;i++) { scanf("%d",&b);sm+=b; D.add(s,i,b);//连向源点的正点权 char tools[10000]; memset(tools,0,sizeof tools); cin.getline(tools,10000); int ulen=0,tool; while (sscanf(tools+ulen,"%d",&tool)==1)//之前已经用scanf读完了赞助商同意支付该实验的费用 {//tool是该实验所需仪器的其中一个 //这一行，你可以将读进来的编号进行储存、处理，如连边。 D.add(i,tool+n,inf); if (tool==0) ulen++; else { while (tool) { tool/=10; ulen++; } } ulen++; } } //连向汇点的负点权 for(int i=1;i<=m;i++)scanf("%d",&a),D.add(i+n,t,a); int flow=0;D.gao(); // cout<<"-----------------------------------"<<endl; //跑完dinic后，从s开始可达的点集为割的一边。只需要找到分界线就是全部的割了 //显然这一题只会出现简单割(与s、t直接相连的割边) for(int i=1;i<=n;i++)//左部图的割边表示不选择改器材 if(!(D.d[s]&&!D.d[i])) cout<<i<<" "; cout<<endl; for(int i=1;i<=m;i++)//右部图的割边就表示的就是选择改器材 if(D.d[i+n]&&!D.d[t]) cout<<i<<" "; cout<<endl; // cout<<sm<<" "<<D.maxflow<<endl; cout<<sm-D.maxflow<<endl; return 0; }
