BZOJ 2360 唯美村落 题解

题目链接：darkbzoj；hydro-bzoj；某离线bzoj题库

题目大意：给定一张 (n) 个点的有向图，点有点权，保证无自环，如果图中存在点 (u,v,a,b)，使得存在 (u o a,u o b,v o a)，则一定有 (v o b)，求这张图有没有哈密尔顿回路，如果没有，输出 -1，如果有，输出按照点权字典序排序最大的。

(nleq 2 imes 10^4)

---

题解：考虑拆点，将每一个点拆成入点和出点，对于一条有向边 (u o v)，可以转换成从 (u) 的出点连向 (v) 的入点的无向边，容易发现题目的条件满足了以下两个条件：

1. 这是一张二分图，并且这张二分图的每一个联通块都是完全二分图；
2. 每一个点的入点和出点都不在同一个联通块内。

这启发我们可以将联通块视作点，一个点的入点所在的联通块向出点所在的联通块连边，因为我们要求的是原图的哈密尔顿回路，所以就相当于我们要经过该图中的所有的边，就是需要求出该图的一个欧拉路径，有向图的欧拉回路是有线性做法了。

至于如何保证字典序最大，按照边排序即可。

时间复杂度 (O(nlog n))。

代码：

#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
const int Maxn=20000;
int n,m;
int fa[Maxn<<1|5];
void init(){
	for(int i=1;i<=(n<<1);i++){
		fa[i]=i;
	}
}
int find(int x){
	if(x==fa[x]){
		return x;
	}
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	int fa_x=find(x),fa_y=find(y);
	if(fa_x==fa_y){
		return;
	}
	fa[fa_y]=fa_x;
}
int deg[Maxn<<1|5];
std::vector<std::pair<int,int> > g[Maxn<<1|5];
int p[Maxn<<1|5];
int a[Maxn+5];
bool cmp(std::pair<int,int> x,std::pair<int,int> y){
	return a[x.second]>a[y.second];
}
void add_edge(int from,int to,int w){
	deg[from]++,deg[to]--;
	g[from].push_back(std::make_pair(to,w));
}
int ans[Maxn+5],ans_len;
void work_dfs(int u){
	while(p[u]<(int)g[u].size()){
		int t=p[u];
		p[u]++;
		work_dfs(g[u][p[u]-1].first);
		ans[++ans_len]=g[u][t].second;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	init();
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		merge(v,u+n);
		if(w==2){
			merge(u,v+n);
		}
	}
	for(int i=1;i<=n;i++){
		add_edge(find(i),find(i+n),i);
	}
	for(int i=1;i<=(n<<1);i++){
		if(deg[i]!=0){
			puts("-1");
			return 0;
		}
		std::sort(g[i].begin(),g[i].end(),cmp);
	}
	int pos=-1;
	for(int i=1;i<=n;i++){
		if(pos==-1||a[i]>a[pos]){
			pos=i;
		}
	}
	work_dfs(find(pos));
	if(ans_len!=n){
		puts("-1");
		return 0;
	}
	for(int i=ans_len;i>0;i--){
		printf("%d
",ans[i]);
	}
	return 0;
}