第一次做最小割，不是很理解。
https://www.luogu.org/problemnew/show/P1361
要把东西分进两类里，好像可以应用最小割的模板，其中一类A作为源点，另一类B作为汇点，价值就是边的容量。
然后最小割一定会割断每个中间结点的两边的其中一边，这样最大价值就顺带求出来了。
在这道题里面额外还有某些点成组出现的额外价值。题解的办法是分别虚拟两个结点代表两个集合，源点到集合a的容量是其价值，然后从a连到他的附属结点各边容量为无穷。无穷的边不能被最小割割断。所以要么是把a的从属结点到t的边全部割断，然后多出来a的附加价值，要么是把s到a的附加价值边割断使a不能流向t。画个图发现很巧妙。
#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2e6+5,M=2e6+5; int n,m,s,t,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N]; void add(int u,int v,int w) { ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w; } void addedge(int u,int v,int w) { add(u,v,w),add(v,u,0); } int bfs(int s,int t) { memset(dep,0,sizeof(dep)); memcpy(cnr,lnk,sizeof(lnk)); std::queue<int> q; q.push(s),dep[s]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=lnk[u];i;i=nxt[i]) { int v=ter[i]; if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1; } } return dep[t]; } int dfs(int u,int t,int flow) { if(u==t) return flow; int ans=0; for(int i=cnr[u];i&&ans<flow;i=nxt[i]) { cnr[u]=i; int v=ter[i]; if(val[i]&&dep[v]==dep[u]+1) { int x=dfs(v,t,std::min(val[i],flow-ans)); if(x) val[i]-=x,val[i^1]+=x,ans+=x; } } if(ans<flow) dep[u]=-1; return ans; } ll dinic(int s,int t) { ll ans=0; while(bfs(s,t)) { ll x; while((x=dfs(s,t,1<<30))) ans+=x; } return ans; } int main() { ll sum=0; scanf("%d",&n); s=0,t=10000; for(int i=1;i<=n;i++){ int u=s,v=i,w; scanf("%d",&w); addedge(u,v,w); sum+=w; } for(int i=1;i<=n;i++){ int u=i,v=t,w; scanf("%d",&w); addedge(u,v,w); sum+=w; } int m; scanf("%d",&m); int id=n+1; while(m--) { int k; scanf("%d",&k); int w1,w2; scanf("%d%d",&w1,&w2); addedge(s,id,w1); addedge(id+1,t,w2); sum+=w1+w2; for(int i=0;i<k;i++){ int x; scanf("%d",&x); addedge(id,x,0x3f3f3f3f); addedge(x,id+1,0x3f3f3f3f); } id+=2; } printf("%lld\n",sum-dinic(s,t)); return 0; }
原文：https://www.cnblogs.com/Yinku/p/10618586.html