题目传送门1
题目传送门2
题意
洛谷那题比较简明,就是多张图(\(d \leq 200\)),每次给某张图加一条边,询问加完后有多少点对在所有图都联通。
题解
翻了很多题解都是用的hash做法,具体而言就是如果两个点在某张图联通,那么他们在该图并查集有相同根节点。将每个点在所有图的根节点构成一个字符串,只有字符串相同时,两个点才能在所有图都联通, 用hash解决。 其实很聪明,但我在没看过原题的情况下确想不出,赛时写了一个离线反着删边的做法,现在在洛谷是最优解,不过理论复杂度应该一样?
所以来一个非哈希的题解吧:我们考虑先把所有边建好,再反着删除边,这样做的好处是,如果你正着加边,需要所有图中都联通才能联通。而反着删除边,只要一个图被割裂就割裂了。
这是一个出发点,但实际情况比较复杂,我们如何删除一条边呢?考虑加边时,如果一条边连接的两个点已经联通,那么这条边加入是无意义的,因为反删除时这条边反而会提前删除。所以在按秩合并下,所有有意义的加边构成一颗树,图边和并查集树边一一对应,问题在于当你断开一条树边时,原来的树被分成两颗子树,但这两颗子树中的某些点对可能之前就在其他并查集树上被隔离了,所以你不好直接去统计答案。
这时候你容易发现,由于启发式合并的复杂度,你可以允许在删除一条边将树一分为二时,遍历小的那一颗子树。(读自证)但我们还不知道能用这个复杂度做些什么。
我们考虑加完所有边之后,暴力的跑一遍答案,这时候我们就得到了所有图的共有联通块集合,每一个联通块在所有图都是联通的,并且每一个点都属于一个共有联通块(再不济它自己也能构成一个连通块)。
我们考虑删边的同时维护这个连通块集合,每次删边时,一颗并查集树一分为二棵子树,对于连通块集合中的任意一个联通块,要么不在这颗树上没影响,要么连通块的点都在其中一颗子树上,仍然联通没影响。最后就是有影响的情况,这个联通块的点分布在两颗子树上,删边会将其一分为二(这里其实就是反着做,一个联通块只要在一个图被分开就被分开了的优点)。
这样我们遍历小的那颗子树,对于其中每一个点所在的连通块,如果都在这颗子树上则不管,否则还有大子树的部分,但由于我们维护了每个联通块的总大小,知道小子树的部分也就知道了大子树部分,直接一分为二就可以,并且统计答案,还是只用枚举小子树就行。
复杂度我不太会算,一个上界应该是\(nd \ log (nd)\),足以通过, 但实际由于总操作次数是m级别的,我也不太会算。
btw,虽然赛时代码很烂,但洛谷上是最优解(
实现
赛时代码完全看不了,因为很多细节是边写边考虑的,变量名完全不知道叫什么乱取。。。。。
所以稍微讲一下实现把,代码之所以这么烂,主要是最后建完边之后求并查集的交集那里搞得太复杂了,因为启发式和并你不能很好的清空数组,每次你只能遍历一遍清空,再遍历一遍计算,然后这交集也不算好求把,就写太烂了,读者可以教博主怎么更好的去求这个东西。 我这里是对于并查集的每一个联通块, 考虑它在另一个并查集的中的分布,对于分布相同的就连接起来。
#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <tuple>
#define ll long long
#define edge tuple<int, int, int>
using namespace std;
int read(){
int num=0, flag=1; char c=getchar();
while(!isdigit(c) && c!='-') c=getchar();
if(c == '-') flag=-1, c=getchar();
while(isdigit(c)) num=num*10+c-'0', c=getchar();
return num*flag;
}
const int N = 5e4+20;
const int M = 110;
int T;
int n, m, d, q;
struct Tree{
int fa[N], dep[N];
vector<int> son[N];
void clear(){
for(int i=1; i<=n; i++) fa[i]=i, dep[i]=1;
for(int i=1; i<=n; i++) son[i].clear();
}
int find(int x){
while(fa[x] != x) x = fa[x];
return x;
}
void merge(int u, int v){
u=find(u), v=find(v);
if(u == v) return ;
if(dep[u] > dep[v]) swap(u, v);
fa[u] = v;
son[v].push_back(u);
dep[v] = max(dep[v], dep[u]+1);
}
}t[M];
int root = M-3;
int lroot = (root ^ 1);
vector<edge > Q;
int vis[N];
int col[N], siz[N];
int cnt = 0;
int ctc[N];
ll res[110000];
int qid[110000];
vector<int> tp[N];
vector<int> pt[N];
vector<int> pp;
void dfs(int x, int w){
pp.push_back(x);
for(int nex : t[w].son[x]){
if(t[w].fa[nex] == x)
dfs(nex, w);
}
}
void solve(){
ll ans = 0;
n=read(), m=read(), d=read()+1, q=read();
{
Q.clear();
t[root].clear();
for(int i=1; i<=n; i++) siz[i] = 0;
for(int i=1; i<=d; i++) t[i].clear();
for(int i=1; i<=q; i++) res[i]=-1;
}
for(int i=1; i<=m; i++){
int u=read(), v=read();
for(int j=1; j<=d; j++){
if(t[j].find(u) != t[j].find(v)){
t[j].merge(u, v);
}
}
}
for(int i=1; i<=q; i++){
int u=read(), v=read(), w=read();
u=t[w].find(u), v=t[w].find(v);
if(u == v) continue;
Q.push_back((edge){u, v, w});
qid[Q.size()-1] = i;
t[w].merge(u, v);
}
for(int i=1; i<n; i++) t[root].merge(i, i+1);
for(int id=1; id<=d; id++){
lroot = (root ^ 1);
t[lroot].clear();
for(int i=1; i<=n; i++) pt[i].clear();
for(int i=1; i<=n; i++) pt[t[id].find(i)].push_back(i);
for(int i=1; i<=n; i++){
for(int x : pt[i]){
int fa = t[root].find(x);
vis[fa] = 0;
tp[fa].clear();
}
for(int x : pt[i]){
int fa = t[root].find(x);
tp[fa].push_back(x);
}
for(int x : pt[i]){
int fa = t[root].find(x);
if(vis[fa]++) continue;
for(int j=0; j+1<tp[fa].size(); j++){
t[lroot].merge(tp[fa][j], tp[fa][j+1]);
}
}
}
swap(root, lroot);
}
// for(int i=1; i<=n; i++) pt[i].clear();
cnt = 0;
for(int i=1; i<=n; i++) ctc[i] = 0;
for(int i=1; i<=n; i++){
col[i] = t[root].find(i);
if(ctc[col[i]] == 0) ctc[col[i]] = ++cnt;
col[i] = ctc[col[i]];
siz[col[i]]++;
}
for(int i=1; i<=n; i++) ans += 1ll*siz[i]*siz[i];
res[q+1] = ans;
for(int id=((int)Q.size())-1; id>=0; id--){
int u=get<0>(Q[id]), v=get<1>(Q[id]), w=get<2>(Q[id]);
if(t[w].fa[u] != v) swap(u, v);
t[w].fa[u] = 0;
pp.clear();
dfs(u, w);
for(int x : pp){
vis[x] = 0;
pt[col[x]].clear();
}
for(int x : pp){
pt[col[x]].push_back(x);
}
for(int x : pp){
if(vis[x]) continue;
int tcol = col[x];
for(int y : pt[tcol]) vis[y] = 1;
if(pt[tcol].size() == siz[tcol]) continue;
int ncol = ++cnt;
siz[ncol] = 0;
for(int y : pt[tcol]){
col[y] = ncol;
siz[ncol]++;
}
ans -= 1ll*siz[tcol]*siz[tcol];
siz[tcol] -= siz[ncol];
ans += 1ll*siz[ncol]*siz[ncol] + 1ll*siz[tcol]*siz[tcol];
}
// printf("%lld\n", (ans-n)/2);
res[qid[id]] = ans;
}
for(int i=q; i>=1; i--) {
if(res[i] == -1) res[i] = res[i+1];
}
for(int i=1; i<=q; i++) printf("%lld\n", (res[i+1]-n)/2);
}
int main(){
T = read();
while(T--){
solve();
}
return 0;
}
标签:联通,pt,int,Bajtocja,ONTAK2015,P8026,ncol,siz,tcol
From: https://www.cnblogs.com/ltdjcoder/p/18348544