[CF 343E]Pumping Stations解题报告

题目翻译

http://cogs.pro/cogs/problem/problem.php?pid=1994

题解

首先，有一个东西叫Gomory-Hu（戈莫里-胡）树。就是说，对于一张题中这样的图可以建出来一棵树，使得图中s~t的最小割等于树中s~t路径上的最小边权。

那么问题来了：怎么建树呢？

有两篇资料：

Wiki百科：

http://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree

yangff的博客：

http://yangff.logdown.com/posts/141380-gomoryhu-tree

如果你看完之后还不知道怎么建，不用担心，你不是一个人……

其实这个建树过程写出来并不难，看一下代码就知道了。大致思路是：一开始所有点都在同一个集合内。然后每次选一个集合，对其中两个点做最小割，按照源汇集分割这个集合，并添加一条边。最后所有集合都剩下一个点，树也就建完了。共需要做O(n)次最大流。

现在有了这棵树，应该怎么办呢？

很简单：选择树中权值最小的边，那么最优解一定是先在一侧走完，再经过这条边，再走另外一侧（只经过该权值最小的边一次，最优方案必然如此）。然后分成两部分递归下去即可。

所以这篇题解的核心其实是贴一下Gomory-Hu树的代码，相信我，代码真的非常简单……

代码

#include
#include
#include
#include
#include
#include
using namespace std;
const int SIZEN=210,INF=0x7fffffff/2;
class EDGE{
public:
	int from,to,cap,flow;
};
vector edges;
vector c[SIZEN];
int S,T;
bool visit[SIZEN]={0};
int depth[SIZEN]={0};
int cur[SIZEN]={0};
void clear_graph(void){
	edges.clear();
	for(int i=0;i Q;
	Q.push(S);visit[S]=true;depth[S]=0;
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=0;inow.flow){
				visit[now.to]=true;
				depth[now.to]=depth[x]+1;
				Q.push(now.to);
			}
		}
	}
	return visit[T];
}
int DFS(int x,int a){
	if(x==T||!a) return a;
	int flow=0,cf=0;
	for(int i=cur[x];i
建树就是build_tree函数。

题目翻译

题解

代码

发表回复 取消回复

发表回复取消回复