[网络流]最大权闭合图(转载)来自: http://hi.baidu.com/%C6%AE%BB%A8%C4%EA%B4%FA/blog/item/45d4bb1765e7044721a4e960.html
以下内容参考 胡伯涛 《最小割模型在信息学竞赛中的应用》,感谢他为我们提供这么优秀的论文。
看不懂以上论文的同学,可以试试看一下以下内容,本文无大量的数学符号,方便阅读理解。
首先我们由一道题来引入,见 [线性规划与网络流24题
2] 太空飞行计划问题 。
这道题中,实验依赖于仪器,而实验和仪器都有权值,且仪器为负,实验为正。
这里闭合图的概念就很好引出了。在一个图中,我们选取一些点构成集合,记为V,且集合中的出边(即集合中的点的向外连出的弧),所指向的终点(弧头)也在V中,则我们称V为闭合图。最大权闭合图即在所有闭合图中,集合中点的权值之和最大的V,我们称V为最大权闭合图。
上图中闭合图有
{5}、{2,5}、{4,5}
{2,4,5}、{3,4,5}
{1,2,3,4,5}、{1,2,4,5}
最大权闭合图为{3,4,5}。
针对本题而言,我们将实验与仪器间连一条有向边,实验为起点(弧尾),仪器为终点(弧头)。则如果我们选择一个闭合图,那么这个闭合图中包含的实验所需要的仪器也最这个闭合图里。而最大权闭合图即为题目的解。
了解了最大权闭合图的概念,接下来我们就需要知道如何求最大权闭合图。
首先我们将其转化为一个网络(现在不要问为什么,接下来会证明用网络可以求解)。构造一个源点S,汇点T。我们将S与所有权值为正的点连一条容量为其权值的边,将所有权值为负的点与T连一条容量为其权值的绝对值的边,原来的边将其容量定为正无穷。
上图即被转化为如左图网络。
首先引入结论,最小割所产生的两个集合中,其源点S所在集合(除去S)为最大权闭合图,接下来我们来说明一些结论。
- 证明:最小割为简单割。
引入一下简单割的概念:割集的每条边都与S或T关联。(请下面阅读时一定分清最小割与简单割,容易混淆)
那么为什么最小割是简单割呢?因为除S和T之外的点间的边的容量是正无穷,最小割的容量不可能为正无穷。所以,得证。
- 证明网络中的简单割与原图中闭合图存在一一对应的关系。(即所有闭合图都是简单割,简单割也必定是一个闭合图)。
证明闭合图是简单割:如果闭合图不是简单割(反证法)。那么说明有一条边是容量为正无穷的边,则说明闭合图中有一条出边的终点不在闭合图中,矛盾。
证明简单割是闭合图:因为简单割不含正无穷的边,所以不含有连向另一个集合(除T)的点,所以其出边的终点都在简单割中,满足闭合图定义。得正。
- 证明最小割所产生的两个集合中,其源点S所在集合(除去S)为最大权闭合图。
首先我们记一个简单割的容量为C,且S所在集合为N,T所在集合为M。
则C=M中所有权值为正的点的权值(即S与M中点相连的边的容量)+N中所有权值为负的点权值的绝对值(即N中点与T中点相连边的容量)。记(C=x1+y1);(很好理解,不理解画一个图或想象一下就明白了)。
我们记N这个闭合图的权值和为W。
则W=N中权值为正的点的权值-N中权值为负的点的权值的绝对值。记(W=x2-y2);
则W+C=x1+y1+x2-y2。
因为明显y1=y2,所以W+C=x1+x2;
x1为M中所有权值为正的点的权值,x2为N中权值为正的点的权值。
所以x1+x2=所有权值为正的点的权值之和(记为TOT).
所以我们得到W+C=TOT.整理一下W=TOT-C.
到这里我们就得到了闭合图的权值与简单割的容量的关系。
因为TOT为定值,所以我们欲使W最大,即C最小,即此时这个简单割为最小割,此时闭合图为其源点S所在集合(除去S)。得正。
至此,我们就将最大权闭合图问题转化为了求最小割的问题。求最小割用最小割容量=最大流,即可将问题转化为求最大流的问题。
最大权闭合的求法参看黑书
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- const int maxn=5e3+9,maxm=6e4+9;
- const long long inf=(long long)1<<50;
- int level[maxn],head[maxn],que[maxn];
- int lon;
- struct
- {
- int next,to;
- long long w;
- }e[maxm*10];
- void edgeini()
- {
- memset(head,-1,sizeof(head));
- lon=-1;
- }
- void edgemake(int from,int to,long long w)
- {
- e[++lon].to=to;
- e[lon].w=w;
- e[lon].next=head[from];
- head[from]=lon;
- }
- int makelevel(int s,int t)
- {
- memset(level,0,sizeof(level));
- level[s]=1;
- int top=0;
- que[++top]=s;
- for(int i=1;i<=top;i++)
- {
- int u=que[i];
- if(u==t) return(1);
- for(int k=head[u];k!=-1;k=e[k].next)
- if(!level[e[k].to]&&e[k].w)
- {
- que[++top]=e[k].to;
- level[e[k].to]=level[u]+1;
- }
- }
- return(0);
- }
- long long dfs(int now,long long maxf,int t)
- {
- if(now==t) return(maxf);
- long long ret=0;
- for(int k=head[now];k!=-1;k=e[k].next)
- {
- if(e[k].w&&level[e[k].to]==level[now]+1)
- {
- long long f=dfs(e[k].to,min(maxf-ret,e[k].w),t);
- e[k].w-=f;
- e[k^1].w+=f;
- ret+=f;
- if(ret==maxf) return(ret);
- }
- }
- return(ret);
- }
- long long dinic(int s,int t)
- {
- long long ans=0;
- while(makelevel(s,t)) ans+=dfs(s,inf,t);
- return(ans);
- }
- int flag[maxn];
- int dfs(int t)
- {
- int ret=1;
- flag[t]=1;
- for(int k=head[t];k!=-1;k=e[k].next)
- if(e[k].w>0)
- {
- int u=e[k].to;
- if(!flag[u])
- ret+=dfs(u);
- }
- return(ret);
- }
- int main()
- {
- int n,m;
- while(scanf("%d %d",&n,&m)!=EOF)
- {
- edgeini();
- long long sum=0;
- for(int i=1,tmp;i<=n;i++)
- {
- scanf("%d",&tmp);
- if(tmp>0)
- {
- sum+=tmp;
- edgemake(0,i,tmp);
- edgemake(i,0,0);
- }
- else
- {
- edgemake(i,n+1,-tmp);
- edgemake(n+1,i,0);
- }
- }
- for(int i=1,from,to;i<=m;i++)
- {
- scanf("%d %d",&from,&to);
- edgemake(from,to,inf);
- edgemake(to,from,0);
- }
- memset(flag,0,sizeof(flag));
- long long ans=dinic(0,n+1);
- printf("%d ",dfs(0)-1);
- printf("%lld\n",sum-ans);
- }
- return 0;
- }