Codeforces891CEnvy（MST+并查集的撤销）

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

题目链接 Envy

题意给出一个连通的无向图和若干询问。每个询问为一个边集。求是否存在某一棵原图的最小生成树包含了这个边集。

考虑$kruskal$的整个过程，

当前面$k$条边已经完成操作的时候（就是前$k$小的边已经进行并查集缩点，此时部分点已经形成了若干个连通块）

这个时候突然冒出来一些权值相同并且这个权值大于前$k$条边最大权值的边，问这些边是否能同时被某一棵最小生成树包含。

那我们依次检查这突然冒出来的几条边，在原来的这个并查集的基础上，继续进行缩点操作。

如果这些边在处理的时候没有遇到某条边的两个点在连边之前已经连通的情况，那么这些边能同时被某一棵最小生成树包含。

反之亦然。

对于这道题我们要做的就是把所有询问离线，把每条询问边塞到对应的权值里面。

当我现在要检查权值为$x$的某些同一个询问里的边的时候，首先要保证那些权值小于$x$的边都已经进行了并查集缩点。

然后把这些权值为$x$的某些同一个询问里的边想象成刚刚说的“突然冒出来的几条边”，检查就可以了。

如果不行的话这个询问的$id$的答案就是$NO$了。

因为同一个权值里面可能会有（其实是一般都有）询问id不同的边，那么处理完某一批边之后我们要对询问的时候改动的并查集撤销。

开个栈记录一下即可。

#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 pair <int, int> PII;

const int N = 5e5 + 10;

struct node{
	int x, y, z;
	void scan(){ scanf("%d%d%d", &x, &y, &z);}
} e[N];

struct query{
	int x, y, id;
	friend bool operator < (const query &a, const query &b){
		return a.id < b.id;
	}
};
		
int father[N], ret[N], n, m, qu, now, opnum;
stack <PII> s;
vector <query> v[N];
vector <PII>   g[N];

int getfather(int x){
	if (father[x]){
		s.push(MP(x, father[x]));
		father[x] = getfather(father[x]);
		return father[x];
	}

	else return x;
}

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

void work(int x, int y){
	int fx = gf(x), fy = gf(y);
	if (fx ^ fy) father[fx] = fy;
}

void solve(int cnt, int x, int y){
	while (!s.empty()) s.pop();
	rep(i, x, y){
		int fx = getfather(v[cnt][i].x), fy = getfather(v[cnt][i].y);
		if (fx == fy) ret[v[cnt][i].id] = 1;
		else{
			s.push(MP(fx, father[fx]));
			father[fx] = fy;
		}
	}

	while (!s.empty()){
		father[s.top().fi] = s.top().se;
		s.pop();
	}
}

int main(){

	scanf("%d%d", &n, &m);
	rep(i, 1, m){
		e[i].scan();
		g[e[i].z].push_back(MP(e[i].x, e[i].y));
	}

	scanf("%d", &qu);
	rep(i, 1, qu){
		int opnum;
		scanf("%d", &opnum);
		rep(j, 1, opnum){
			int x;
			scanf("%d", &x);
			v[e[x].z].push_back({e[x].x, e[x].y, i});
		}
	}

	rep(i, 1, 5e5) sort(v[i].begin(), v[i].end());
	rep(i, 1, 5e5){
		for (auto u : g[i - 1]) work(u.fi, u.se);
		int sz = v[i].size();
		if (sz == 0) continue;
		int now = 0;
		while (now < sz){
			int j = now;
			while (j + 1 < sz && v[i][j + 1].id == v[i][j].id) ++j;
			solve(i, now, j);
			now = j + 1;
		}
	}

	rep(i, 1, qu) puts(ret[i] ? "NO" : "YES");
	return 0;
}