ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[AtCoder Beginner Contest 264]E - Blackout 2(离线处理 + 并查集)

2022年8月20日 195点热度 0人点赞 0条评论

题目传送门:E - Blackout 2 (atcoder.jp)

题目 / Problem

有N个城市和M个发电厂,有E条边,第 i 条边连接两个点(可能是城市也可能是发电厂),现在有Q个项目,每个项目会摧毁第x条边,问每个项目之后有多少个城市可以到达发电厂。

思路 / Thought

因为M个发电厂都是等价的,所有可以把这M个发电厂都看作0号点。为了维护“是否可达”这个属性,可以用并查集,但是与此同时还需要一个集合来存储某个祖先的所有儿子。

在合并操作的时候需要将集合也进行合并,合并的规则需要注意:如果有0号点,就将另一个集合合并到0号点,否则将小集合合并到大集合。

我们又注意到,这里是要将边摧毁,也就是将点分离,显然不好操作,我们可以将询问离线,倒过来进行合并。

也就是说“正着分离” = “倒着合并”,将答案保存下来并输出即可。

需要记录一下有哪些点是没参与询问的,作为初始状态,然后从后往前将边一条一条地加入。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9;
int pre[maxn];//0是发电厂 
set<int> s[maxn];//集合 
int N, M, E;

int root(int x){return pre[x] == x ? x : pre[x] = root(pre[x]);}

void Merge(int x,int y)
{
	int rx = root(x), ry = root(y);
	if(rx == ry)return;//如果已经是同一个集合不用合并 
	if(rx > ry)swap(rx, ry);//使得rx < ry 
	if(rx == 0)//如果rx是0合并到0号集合 
	{
		for(auto &i : s[ry])s[rx].insert(i);
		s[ry].clear();
		pre[ry] = 0;
	}else//否则合并到较大集合 
	{
		if(s[rx].size() > s[ry].size())swap(rx, ry);
		for(auto &i : s[rx])s[ry].insert(i);
		s[rx].clear();
		pre[rx] = ry;
	}
}

void solve()
{
	cin >> N >> M >> E;
	for(int i = 1;i <= N; ++ i)
	{
		pre[i] = i;
		s[i].insert(i);
	}
	
	vector<pair<int, int> > v;
	
	v.push_back({0, 0});
	for(int i = 1;i <= E; ++ i)
	{
		int x, y;cin >> x >> y;
		x = x > N ? 0 : x;
		y = y > N ? 0 : y;
		v.push_back({x, y});
	}
	
	bitset<maxn * 3> del;//删除的边
	
	int Q;cin >> Q;
	vector<int> q, ans(Q + 5, 0);
	
	for(int i = 0;i < Q; ++ i)
	{
		int x;cin >> x;
		q.push_back(x);
		del[x] = 1;
	}
	
	int cnt = 0;
	//将未被摧毁的边建立
	for(int i = 1;i <= E; ++ i)if(!del[i])Merge(v[i].first, v[i].second);
	
	for(int i = q.size() - 1;i >= 0; -- i)//反向重建
	{
		ans[i] = s[0].size();
		int x = v[q[i]].first, y = v[q[i]].second;
		Merge(x, y);
	}
	for(int i = 0;i < Q; ++ i)cout << ans[i] << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _ = 1;
	while(_ --)solve();
	
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: atcoder C++ 思维 离线 离线处理 算法竞赛
最后更新:2022年8月20日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号