定義：最大權閉合圖：是有向圖的一個點集，且該點集的所有出邊都指向該集合。即閉合圖內任意點的集合也在改閉合圖內，給每個點分配一個點權值Pu，最大權閉合圖就是使閉合圖的點權之和最大。
最小割建邊方式：源點s和正權的點連接，容量是Pu，負權的點和匯點t相連，容量是-Pu，之間的邊權值inf，過一遍最大流ans，正權之和sum-ans就是最大權閉合圖的值。
例題：HDU3996
題意：給出n個金礦地區，每個金礦地區有mi個礦坑，挖取第i個地區的第j個礦坑需要花費cost[i][j],可以獲得利益value[i][j]，但是有些限制條件，就是想要挖取第i個地區的第j個礦坑之前必須把第ii個地區的第jj個礦坑挖掉.問最大獲益是多少？
分析：共用n*Mi個礦坑，每個點的權值是value[i][j]-cost[i][j]，建邊從第i，j指向ii，jj，表示要選取i，j一定會選取ii，jj。建邊后跑一遍Dinic即可。
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"algorithm"
#include"math.h"
#include"vector"
#include"queue"
#define M 3009
#define inf 1000000000000000LL
#define eps 1e-7
#define pps 1e-18
#define PI acos(-1.0)
#define LL __int64
using namespace std;
struct node
{int u,v,next;LL w;
}edge[M*300];
int t,head[M],dis[M];
int lay[M],num[111][30],work[M];
LL p[M],cost[M];
LL min(LL a,LL b)
{return a<b?a:b;
}
void init()
{t=0;memset(head,-1,sizeof(head));
}
void add(int u,int v,LL w)
{edge[t].u=u;edge[t].v=v;edge[t].w=w;edge[t].next=head[u];head[u]=t++;edge[t].u=v;edge[t].v=u;edge[t].w=0;edge[t].next=head[v];head[v]=t++;
}
int bfs(int S,int T)
{queue<int>q;memset(dis,-1,sizeof(dis));q.push(S);dis[S]=0;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(edge[i].w&&dis[v]==-1){dis[v]=dis[u]+1;if(v==T)return 1;q.push(v);}}}return 0;
}
LL dfs(int cur,LL a,int T)
{if(cur==T)return a;for(int &i=work[cur];~i;i=edge[i].next){int v=edge[i].v;if(edge[i].w&&dis[v]==dis[cur]+1){LL tt=dfs(v,min(a,edge[i].w),T);if(tt){edge[i].w-=tt;edge[i^1].w+=tt;return tt;}}}return 0;
}
LL Dinic(int S,int T)
{LL ans=0;while(bfs(S,T)){memcpy(work,head,sizeof(head));while(LL tt=dfs(S,inf,T))ans+=tt;}return ans;
}
struct st
{int u,v;st(int uu,int vv){u=uu;v=vv;}
};
vector<st>s[M];
int main()
{int Case,n,i,j,k,K,ii,jj,kk=1;scanf("%d",&Case);while(Case--){scanf("%d",&n);for(i=1;i<M;i++)s[i].clear();int cnt=0;init();for(i=1;i<=n;i++){scanf("%d",&lay[i]);for(j=1;j<=lay[i];j++){num[i][j]=++cnt;scanf("%I64d%I64d%d",&cost[cnt],&p[cnt],&K);for(k=1;k<=K;k++){scanf("%d%d",&ii,&jj);s[cnt].push_back(st(ii,jj));}}}init();for(i=1;i<=n;i++){for(j=1;j<=lay[i];j++){for(k=0;k<(int)s[num[i][j]].size();k++){int ii=s[num[i][j]][k].u;int jj=s[num[i][j]][k].v;add(num[i][j],num[ii][jj],inf);}}}LL sum=0;for(i=1;i<=cnt;i++){if(p[i]-cost[i]>0){add(0,i,p[i]-cost[i]);sum+=p[i]-cost[i];}else if(p[i]-cost[i]<0)add(i,cnt+1,cost[i]-p[i]);}LL ans=Dinic(0,cnt+1);printf("Case #%d: ",kk++);printf("%d\n",sum-ans);}return 0;
}
)
)
