题目传送门: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; }
Comments NOTHING