本文共 2991 字，大约阅读时间需要 9 分钟。

闭合图

首先，先了解什么是闭合图。闭合图一般指一个图中点的集合，从该集合中所有的点出发，能到达的点要求都必须在该点集中。也就是说，从该集合中出发，一定要回到该集合中，不能出到集合外。

最大权闭合子图，顾名思义，就是所有闭合子图中点权之和最大的那个，注意这里的权指的是点权，因为闭合图是对于点集而言的。

---

最大权闭合子图

了解完概念后，要知道如何求最大权闭合子图。大体的思路是借助最小割模型，让每一种闭合图通过变形后都能和一种割相对应，这样求最大权就是求最小割。

具体做法

构造一个新的流网络，建一个源点s和汇点t，从s向原图中所有点权为正数的点建一条容量为点权的边，从点权为负数的点向t建一条容量为点权绝对值的边，原图中各点建的边都建成容量为正无穷的边。然后求从s到t的最小割，再用所有点权为正的权值之和减去最小割，就是我们要求的最大权值和了。

证明

简单证明，如果不想看证明的可跳过。

如何从最大权闭合子图转化到最小割的呢？首先我们要知道简单割的定义，简单割指的是割集的所有边都是从s出发的边或终点是t的边。由此，我们知道在上述建图方式中的最小割一定是一个简单割，因为其图内部的边的流量是正无穷，所以最小割集一定不包含内部的边，是一个简单割。 然后我们需要证明闭合子图和简单割是一一对应的，从而我们求闭合子图的最值就是简单割的最小值，也就是建的新图的最小割。 我们假设一个闭合子图是v，流网络分成两个集合S和T，构成一个割集的情况。S包含的是v+s（闭合子图的点+源点）；T包含的是剩下的所有点（闭合子图外的点+汇点）。在这种情况下闭合子图v就和这个割[S，T]相对应，且这个割是个简单割：当前割的割集是S集合到T集合的所有边的集合，割集内一定不会出现原图内部的边，因为从S集合出发，若起点是s，则一定不包含原图内部的边，若起点是v，根据闭合子图的定义，回到的一定是v中的点，所以不包含到T集合中的点，因此该割一定是简单割。

这样我们就将闭合子图问题转化成了割的问题了，然后我们就要看看数量关系，找到最大权闭合子图和最小割间的数量表达式，就可以借助最小割模型计算最大权闭合子图了。

首先我们要找到最小割的计算表达式，下面是割集的所有情况： 我们将原图中的点分为两个集合，v₁和v₂，v₁是闭合子图的点集，v₂是原图中剩下的所有点，因此割的所有情况共有四种（S集合到T集合共四种情况），其中有两种情况不存在，第①种情况不存在是因为我们在建图时就不会建s到t的边，第②种情况不存在是根据闭合子图的定理，从v₁出发的点一定会回到v₁，不会到v₂。这样割集就只剩两种情况s到v₂和v₁到t，根据见图方式可得：前者的容量和是v₂中所有点权为正的和，后者容量和是v₁中所有点权为负数的和的相反数，割集的容量之和就是v₂中所有点权为正的和+v₁中所有点权为负数的和的相反数。

然后我们再看我们要求的闭合子图权值之和的计算表达式：最大权值和就等于v₁中所有的权值和，即v₁中所有点权为正的和+v₁中所有点权为负的和。

我们将上面求出来的两个表达式相加可得：割集容量之和+闭合子图权值之和=原图中所有点权为正数的点权之和（后面的相加后刚好抵消）。而等式的右边是个定值，我们为使闭合子图权值最大化，所以我们就要使得割集容量之和最小化，即求最小割的大小，再用所有点权为正的权值之和减去最小割，就是我们要求的最大权值了。

---

例题

原题链接

思路

我们将中转站的成本记为负值，记成该点的点权，再将用户的收益记为记为该点的点权，然后从每一个用户向两个所需的中转站连一条有向边。之后就是求最大权闭合子图的模板了。最大权之和就是最大收益。

#include
   
    #include
    
     #include
     
      using namespace std;const int N = 55010,M = (N+2*50000)*2+10,INF = 0x3f3f3f3f;int n,m,s,t,sum,dis[N],cur[N];int e[M],w[M],ne[M],h[N],idx;	//链式前向星建图void add(int a,int b,int c)	//建图模板{
   	e[idx] = b;	w[idx] = c;	ne[idx] = h[a];	h[a] = idx++;	e[idx] = a;	w[idx] = 0;	ne[idx] = h[b];	h[b] = idx++;}bool bfs()		//dinic模板{
   	queue
      
        q;	memset(dis,-1,sizeof dis);	q.push(s);	dis[s] = 0;	cur[s] = h[s];	while(q.size())	{
   		int u = q.front();		q.pop();		for(int i = h[u];~i;i = ne[i])		{
   			int v = e[i];			if(dis[v] == -1 && w[i])			{
   				dis[v] = dis[u] + 1;				cur[v] = h[v];				if(v == t)					return 1;				q.push(v);			}		}	}	return 0;}int dfs(int u,int limit){
   	if(u == t)		return limit;	int flow = 0;	for(int i = cur[u];~i;i = ne[i])	{
   		int v = e[i];		cur[u] = i;		if(dis[v] == dis[u]+1 && w[i])		{
   			int minf = dfs(v,min(w[i],limit-flow));			w[i] -= minf;			w[i^1] += minf;			flow += minf;			if(flow == limit) 				return flow;		}	}	return flow;}int dinic(){
   	int ans = 0;	while(bfs())		ans += dfs(s,INF);	return ans;}int main(){
   	cin >> n >> m;	memset(h,-1,sizeof h);	s= 0,t = n+m+1;	for(int i = 1;i <= n;i++)	{
   		int p;		cin >> p;		add(m+i,t,p);		//中转站到汇点建边	}	for(int i = 1;i <= m;i++)	{
   		int a,b,c;		cin >> a >> b >> c;		add(i,m+a,INF);		//内部的边建成无穷大		add(i,m+b,INF);		add(s,i,c);		//源点到用户建边		sum += c;		//计算点权为正的权值之和	}	cout << sum-dinic() << endl;	//正数的点权和减去最小割就是答案（最大权闭合子图） 	return 0;}
      
     
    
   

转载地址：http://gfbki.baihongyu.com/