讲讲怎样保存方案和输出:
一个结论就是假如我们跑的是 Dinic 那么我们最后一次网络流（这一次网络流并没有起任何作用，只是确认了无更多残余流量可以退出了。）中所有被分到层的都一定被选上了。
没有更多残余流量其实意味着这个图已经被割成了两部分，一个实验如果有层数意味着它没有被割掉（被选上了），一个仪器如果有层数意味着它已经被割掉了（也是被选上了）。
于是只要在最后输出所有有层数的点就行了。
我的代码
#include<bits/stdc++.h> using namespace std; const int N=30000,INF=0x3f3f3f3f; int h[N],f[N],ne[N],e[N],idx; int q[N], d[N], cur[N];//q是队列，d是分成，cur是优化]; int n,m; int fl=0; int S,T; int ans; inline int read() { int X = 0; bool flag = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') flag = 0; ch = getchar(); } while (ch >= '0' && ch <= '9') { X = (X << 1) + (X << 3) + ch - '0'; ch = getchar(); } if (ch == '\n') fl = 1; if (flag) return X; return ~(X - 1); } inline void write(int X) { if(X<0) {X=~(X-1); putchar('-');} if(X>9) write(X/10); putchar(X%10+'0'); } void add(int a,int b,int c) { f[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++; f[idx]=0,e[idx]=a,ne[idx]=h[b],h[b]=idx++; } int bfs() { memset(d, -1, sizeof d); int tt = 0, hh = 0; q[0] = 0, d[0] = 0, cur[0] = h[0];//当前弧是第一个点 while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; ~i; i = ne[i]) { int ver = e[i]; if (d[ver] == -1 && f[i])//当前点没有被搜索，且流量大于0 { d[ver] = d[t] + 1; cur[ver] = h[ver]; //当前点的当前弧 if (ver == T) return true; q[++ tt] = ver; } } } return false; } int find(int u, int limit )//从原点能够流向u这个点的最大流量为limit { if (u == T) return limit;//如果已经到终点了 表示从原点到终点所能流的流量就是limit int flow = 0;//表示从u这个点开始往后流的流量是多少，dfs求，一开始是0的 //我们之前可能搜索u，可能有些路径满了，所以要将所有满的路径跳过 for (int i = cur[u]; ~i && flow < limit; i = ne[i])//如果从u到终点的总流量等于limit就没有必要再搜了，因为起点到u最多就是limit { cur[u] = i;//记录一下当前搜的弧是那个，流到第i条边，说明前面的边都流过了 int ver = e[i]; if (d[ver] == d[u] + 1 && f[i])//流到下一层，且当前弧可流 { //从当前点开始最多可以有多少流量 int t = find(ver, min(f[i], limit - flow)); if (!t) //从这个点到终点没有流量，说明是不可用的,就把这个点删掉 d[ver] = -1;//这个点到终点没有路径 f[i] -= t, f[i ^ 1] += t, flow += t; } } return flow; } int dinic() { int r = 0, flow; //判断如果有增广路并建立出分层图，然后找出所有增广路，将所有流量加起来 while (bfs()) while (flow = find(S, INF)) r += flow; return r; } int main() { memset(h,-1,sizeof h); m=read(); n=read(); S=0; T=n+m+1; for(int i=1;i<=m;i++) { fl=0; int x,y; x=read(); ans+=x; add(S,i+n,x); while(fl!=1) { y=read(); add(i+n,y,INF); } } for(int i=1;i<=n;i++) { int y=read(); add(i,T,y); } int t=dinic(); int l=0,r=0; for(int i=1;i<=m;i++) { if(d[i+n]!=-1) l=i+n; } for(int i=1;i<=n;i++) { if(d[i]!=-1) r=i; } for(int i=1;i<=m;i++) {if(d[i+n]!=-1&&l!=i+n){ cout<<i<<" ";}else if(d[i+n]!=-1&&l==i+n)cout<<i<<"\n";} for(int i=1;i<=n;i++){if(d[i]!=-1&&r!=i){ cout<<i<<" ";}else if(d[i]!=-1&&r==i)cout<<i<<"\n";} cout<<ans-t<<'\n'; } }
