• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Codeforces891CEnvy(MST+并查集的撤销)

原作者: [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;
}

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
基于C#.NET的高端智能化网络爬虫(转)发布时间:2022-07-13
下一篇:
??运算符(C#参考)发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap