首页 > 代码库 > HDU 3879 Base Station（最大权闭合子图）
HDU 3879 Base Station（最大权闭合子图）
经典例题，好像说可以转化成maxflow（n，n+m），暂时只可以勉强理解maxflow（n+m，n+m）的做法。
题意：输入n个点，m条边的无向图。点权为负，边权为正，输出最大权闭合子图的权值。
（最大权闭合子图：图中各点的后继必然也在图中）
构图攻略：将边看做点（有的题边是没有权的，建模稍微有点不同），
对原本的边e[i]（u,v,w）连3条边（S，n+i，w），（n+i，u，inf），（n+i，v，inf）。
对原本的点v，连1条边（v，T，p[v]）。
即正权点与源点连，负权点与汇点连。
求最大流，记所有边的正权和为sum，则sum-maxflow就是答案。
显然，sap图的点有n+m+2，边有(n+m*3)*2。
具体证明推导请移步前辈的论文或者别的网站也有很详细的介绍和步骤。
#include <cstdio>#include <cstring>#include <iostream>#include <cmath>#include <algorithm>#include <vector>#include <string>#include <set>#include <queue>using namespace std;#define ll long long#define MP make_pair#define mxn 56000#define mxe (51000*4*2)#define inf 1e9#define eps 1e-8struct SAP{ int dis[mxn],pre[mxn],gap[mxn],arc[mxn]; int f[mxe],cap[mxe]; int head[mxn],nxt[mxe],vv[mxe],e; void init(){e=0;memset(head,-1,sizeof(head));} void add(int u,int v,int c){ vv[e]=v,cap[e]=c,nxt[e]=head[u],head[u]=e++; vv[e]=u,cap[e]=0,nxt[e]=head[v],head[v]=e++; } ll max_flow(int s,int t,int n){ int q[mxn],j,mindis; ll ans=0; int ht=0,tl=1,u,v; int low; bool found,vis[mxn]; memset(dis,0,sizeof(dis)); memset(gap,0,sizeof(gap)); memset(vis,0,sizeof(vis)); memset(arc,-1,sizeof(arc)); memset(f,0,sizeof(f)); q[0]=t;vis[t]=true;dis[t]=0;gap[0]=1; while(ht<tl){ u=q[ht++]; for(int i=head[u];i!=-1;i=nxt[i]){ v = vv[i]; if(!vis[v]){ vis[v]=true; dis[v]=dis[u]+1; q[tl++]=v; gap[dis[v]]++; arc[v]=head[v]; } } } u=s;low=inf;pre[s]=s; while(dis[s]<n){ found=false; for(int &i=arc[u];i!=-1;i=nxt[i]){ if(dis[vv[i]]==dis[u]-1 && cap[i]>f[i]){ found=true;v=vv[i]; low=min(low,cap[i]-f[i]); pre[v]=u;u=v; if(u==t){ while(u!=s){ u=pre[u]; f[arc[u]]+=low; f[arc[u]^1]-=low; } ans+=low;low=inf; } break; } } if(found) continue; mindis=n; for(int i=head[u];i!=-1;i=nxt[i]){ if(mindis>dis[vv[i]] && cap[i]>f[i]){ mindis=dis[vv[j=i]]; arc[u]=i; } } if(--gap[dis[u]]==0) return ans; dis[u]=mindis+1; gap[dis[u]]++; u=pre[u]; } return ans; }}sap;int p[5050];int main(){ int n,m; while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;++i) scanf("%d",p+i); ll sum = 0; sap.init(); for(int i=1;i<=m;++i){ int a,b,c; scanf("%d%d%d",&a,&b,&c); sap.add(n+m+1,n+i,c); sap.add(n+i,a,inf); sap.add(n+i,b,inf); sum+=c; } for(int i=1;i<=n;++i) sap.add(i,n+m+2,p[i]); ll mf = sap.max_flow(n+m+1,n+m+2,n+m+2); printf("%I64d\n",sum-mf); } return 0;}
HDU 3879 Base Station（最大权闭合子图）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。