自己整理了下hiho上的提示。做了下笔记，并用图例解释了提示中难懂的部分！
这种题目自己想很难想出来的，不过见一次，下次这种模型就简单了！！
#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)的 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<=m;i++)scanf("%d",&a),D.add(i+n,t,a);//连向汇点的负点权 for(int i=1;i<=n;i++) { scanf("%d",&b);sm+=b; D.add(s,i,b);//连向源点的正点权 int l ,x; scanf("%d",&l); while(l--){ scanf("%d",&x); D.add(i,x+n,inf);//中间连边权无穷大 } } int flow=0; D.gao(); // cout<<sm<<" "<<D.maxflow<<endl; cout<<sm-D.maxflow<<endl; return 0; }
