最大权闭合子图

￡神魔★判官ぃ 2022-10-29 12:29 111阅读 0赞

### 闭合图 ###

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

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

--------------------

### 最大权闭合子图 ###

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

#### 具体做法 ####

构造一个新的流网络，建一个源点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集合中的点，因此该割一定是简单割。

这样我们就将闭合子图问题转化成了割的问题了，然后我们就要看看**数量关系**，找到最大权闭合子图和最小割间的数量表达式，就可以借助最小割模型计算最大权闭合子图了。  
首先我们要找到**最小割的计算表达式**，下面是割集的所有情况：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]  
我们将原图中的点分为两个集合，v1和v2，v1是闭合子图的点集，v2是原图中剩下的所有点，因此割的所有情况共有四种（S集合到T集合共四种情况），其中有两种情况不存在，第①种情况不存在是因为我们在建图时就不会建s到t的边，第②种情况不存在是根据闭合子图的定理，从v1出发的点一定会回到v1，不会到v2。这样割集就只剩两种情况s到v2和v1到t，根据见图方式可得：前者的容量和是v2中所有点权为正的和，后者容量和是v1中所有点权为负数的和的相反数，割集的容量之和就是**v2中所有点权为正的和**\+**v1中所有点权为负数的和的相反数**。

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

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

--------------------

### 例题 ###

#### 原题链接 ####

[Acwing961：最大获利][Acwing961]

#### 思路 ####

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

#include<iostream>
    #include<queue>
    #include<cstring>
    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<int> 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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]: /images/20221024/8d1545a6eeb74a6496ba3eecca71e189.png
[Acwing961]: https://www.acwing.com/problem/content/963/