定義：最大權(quán)閉合圖：是有向圖的一個(gè)點(diǎn)集，且該點(diǎn)集的所有出邊都指向該集合。即閉合圖內(nèi)任意點(diǎn)的集合也在改閉合圖內(nèi)，給每個(gè)點(diǎn)分配一個(gè)點(diǎn)權(quán)值Pu，最大權(quán)閉合圖就是使閉合圖的點(diǎn)權(quán)之和最大。

最小割建邊方式：源點(diǎn)s和正權(quán)的點(diǎn)連接，容量是Pu，負(fù)權(quán)的點(diǎn)和匯點(diǎn)t相連，容量是-Pu，之間的邊權(quán)值inf，過(guò)一遍最大流ans，正權(quán)之和sum-ans就是最大權(quán)閉合圖的值。

例題：HDU3996

題意：給出n個(gè)金礦地區(qū)，每個(gè)金礦地區(qū)有mi個(gè)礦坑，挖取第i個(gè)地區(qū)的第j個(gè)礦坑需要花費(fèi)cost[i][j],可以獲得利益value[i][j]，但是有些限制條件，就是想要挖取第i個(gè)地區(qū)的第j個(gè)礦坑之前必須把第ii個(gè)地區(qū)的第jj個(gè)礦坑挖掉.問(wèn)最大獲益是多少？

分析：共用n*Mi個(gè)礦坑，每個(gè)點(diǎn)的權(quán)值是value[i][j]-cost[i][j]，建邊從第i，j指向ii，jj，表示要選取i，j一定會(huì)選取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; }

轉(zhuǎn)載于:https://www.cnblogs.com/mypsq/p/4348097.html

總結(jié)

以上是生活随笔為你收集整理的最大权闭合图hdu3996的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。