题面
https://www.luogu.org/problemnew/show/P2762
最大权闭合子图，正连$S$，负连$T$。
注意最小割方案的输出（摘自刘汝佳《紫书》）。
一个割，就是把点集$V$分成$S$和$T$，让$s \in S$，$t \in T$，割的流量就是跨越$S$和$T$的所有边的容量之和。
最后一次$bfs$结束之后，有标号的点在$S$中，没标号的点（$d[x]=INF$）在$T$中。
#include<cstdio> #include<cstring> #include<iostream> #include<vector> #include<queue> #define ri register int #define N 200 #define INF 1000000007 #define S 0 #define T (n+m+1) using namespace std; int m,n,x; char tools[10000]; int an[N]; struct graph { vector<int> to,w; vector<int> ed[N]; int cur[N],d[N],col[N]; void add_edge(int u,int v,int w1) { to.push_back(v); w.push_back(w1); ed[u].push_back(to.size()-1); to.push_back(u); w.push_back(0 ); ed[v].push_back(to.size()-1); } bool bfs() { queue<int> q; memset(d,0x3f,sizeof(d)); d[0]=0; q.push(0); while (!q.empty()) { int x=q.front(); q.pop(); for (ri i=0,l=ed[x].size();i<l;i++) { int e=ed[x][i]; if (w[e] && d[x]+1<d[to[e]]) { d[to[e]]=d[x]+1; q.push(to[e]); } } } return d[T]<INF; } int dfs(int x,int limit) { if (x==T || !limit) return limit; int tot=0; for (ri &i=cur[x];i<ed[x].size();i++) { int e=ed[x][i]; if (d[to[e]]==d[x]+1 && w[e]) { int f=dfs(to[e],min(limit,w[e])); if (!f) continue; w[e]-=f; w[1^e]+=f; tot+=f; limit-=f; if (!limit) return tot; } } return tot; } int dinic() { int ret=0; while (bfs()) { memset(cur,0,sizeof(cur)); ret+=dfs(S,INF); } return ret; } } G; int main(){ cin>>m>>n; int sum=0; for (ri i=1;i<=m;i++) { cin>>x; sum+=x; G.add_edge(S,i,x); memset(tools,0,sizeof tools); cin.getline(tools,10000); int ulen=0,tool; while (sscanf(tools+ulen,"%d",&tool)==1) { if (tool==0) ulen++; else { G.add_edge(i,m+tool,INF); while (tool) tool/=10,ulen++; } ulen++; } } for (ri i=1;i<=n;i++) cin>>x,G.add_edge(m+i,T,x); int ans=sum-G.dinic(); for (ri i=0;i<G.to.size();i+=2) { if (G.d[G.to[i]]<INF^G.d[G.to[i^1]]<INF) { if (G.to[i]==S) an[G.to[i^1]]=1; if (G.to[i^1]==S) an[G.to[i]]=1; if (G.to[i]==T) an[G.to[i^1]]=1; if (G.to[i^1]==T) an[G.to[i]]=1; } } for (ri i=1;i<=m;i++) if (!an[i]) cout<<i<<" "; puts(""); for (ri i=1;i<=n;i++) if (an[i+m]) cout<<i<<" "; puts(""); cout<<ans<<endl; }转载于:https://www.cnblogs.com/shxnb666/p/11181845.html
