Hihocoder 1561 观光旅行（启发式合并+贪心）

题目链接 Hihocoder 1561

 

首先对原图求$MST$

我们发现某条边成为某两个点的关键路径的必要条件是这条边是最小生成树的树边。

所以我们求$MST$的同时进行启发式合并。

把$size$小的子树合并到$size$大的子树当中就可以了。

接下来是处理询问。

对于一条边，如果他不是最小生成树的树边，则答案为$0$ $0$

考虑这条边的两边的所有点。

我们先在$B$集合中求出最大的$y$

然后在$A$集合中求出最大的小于$y$的$x$

然后再在$B$集合中求出最小的大于$x$的$y$

这样就符合了题目的这个条件：

$x < y$

且如果有多个满足条件的 $x$ 和 $y$，输出其中 $x$ 最大的，如果还有多个满足条件的，输出其中 $y$ 最小的。

时间复杂度 $O(nlog^{2}n)$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b)	for (int i(a); i >= (b); --i)
#define MP		make_pair
#define fi		first
#define se		second

typedef long long LL;

const int N = 2e5 + 10;

int father[N], sz[N];
set <int> s[N];
int n, m;
pair <int, int> ans[N << 1];

struct node{
	int x, y, z, id;
	void scan(){ scanf("%d%d%d", &x, &y, &z);}
	friend bool operator < (const node &a, const node &b){
		return a.z < b.z;
	}
} e[N << 1];

int getfather(int x){
	return father[x] ? father[x] = getfather(father[x]) : x;
}

void update(int i, int x, int y){
	if (!s[x].size()) return;
	if (!s[y].size()) return;

	int ny = *--s[y].end();
	set <int> :: iterator it =  s[x].lower_bound(ny);
	if (it == s[x].begin()) return;

	int px = *--it;
	int py = *s[y].lower_bound(px);

	if (px > ans[i].fi || px == ans[i].fi && py < ans[i].se) ans[i] = MP(px, py); 
}

int main(){

	scanf("%d%d", &n, &m);
	rep(i, 1, n) sz[i] = 1;
	rep(i, 1, n) s[i].insert(i);

	rep(i, 1, m){
		e[i].scan();
		e[i].id = i;
	}

	sort(e + 1, e + m + 1);
	rep(i, 1, m){
		int x = e[i].x, y = e[i].y;
		int fa = getfather(x);
		int fb = getfather(y);

		if (fa == fb) continue;
		if (sz[fa] < sz[fb]) swap(fa, fb), swap(x, y);

		update(e[i].id, fa, fb);
		update(e[i].id, fb, fa);

		for (auto it : s[fb]) s[fa].insert(it);

		s[fb].clear();
		father[fb] = fa;
		sz[fa] += sz[fb];
	}

	rep(i, 1, m) printf("%d %d
", ans[i].fi, ans[i].se);
	return 0;
}