OI - Mst(BZOJ) | Lucky_Glass's Blog
0%

OI - Mst(BZOJ)

“你会并查集吗?”
“当然会”
“不 你不会” (;′⌒`)


# 题面

点击展开/折叠 题面

给出一个 $n$ 点 $m$ 边的无向图,进行 $q$ 次询问。

每次询问删除原图中的一条边,求剩下的图中最小生成树的大小,或指出图不连通。每次询问独立,即每次删边都是从一开始输入的图中删除。


# 解析

最小生成树有一种生成方法叫做破圈,经常用来解决一些动态加边的生成树问题。在尝试加入一条边的时候,若两端已连通,则需要找到对应的环。

换句话说,设一条边 $(u,v)$ 没有出现在生成树中,加上该边会形成环 $C$;若生成树中的边 $e\in C$ 被删掉了,则可以用 $(u,v)$ 代替 $e$。

于是就有一个基本的想法,即先生成一棵最小生成树,然后对于每条不在生成树上的边 $t$,找到对应环上的生成树中的边 $e$,维护 $f_e\leftarrow\min\{f_e,w_t\}$。

然后就感到可以树链剖分,但是这是 $O(n\log^2 n)$ 的,既然还有 $O(n\log n)$ 的算法就继续优化。

因为 $f_e$ 是取 min,则如果按 $w_t$ 从小到大更新 $f_e$,则 $f_e$ 在第一次赋值后就不再更新了,所以下一次碰到 $e$ 这条边时就可以直接 pass 掉。

直接爬父亲节点,遇到已经赋值的边就 pass,这样每条生成树上的边只遍历一次。

如何实现 pass 掉已经赋值的边?可以理解为一个指针 nxt[u],指向 $u$ 向父亲方向爬,只经过已经赋值的边,能够爬到哪个点。当一条边 $(u,v)$ 被赋值($u$ 是 $v$ 的儿子),则把 nxt[u] 指向 $v$,以及原来 nxt[z]=u 的 $z$ 的 nxt[z] 也更新为 $v$。

这样的一个链表用并查集最方便实现了~

别的没了,就注意判一下原图是否连通……


# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int Read(){
register int r=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
return r;
}

#define cs const int &
const int N=50005,M=100005;

struct GRAPH{
int head[N],to[N<<1],nxt[N<<1],ncnt;
void AddEdge(cs u,cs v){
int p=++ncnt,q=++ncnt;
nxt[p]=head[u],to[p]=v,head[u]=p;
nxt[q]=head[v],to[q]=u,head[v]=q;
}
inline int operator [](cs u){return head[u];}
}Gr;

struct DSU{
int fa[N];
void Init(int siz){for(int i=1;i<=siz;i++) fa[i]=i;}
inline int Find(cs u){return fa[u]==u? u:fa[u]=Find(fa[u]);}
inline bool Merge(int u,int v){
u=Find(u),v=Find(v);
if(u==v) return false;
fa[u]=v;
return true;
}
}Ds;

int n,m,org;
int edg[M][3],id[M],anc[N][20],dep[N],tag[N];
bool del[M];

inline bool cmp(cs a,cs b){return edg[a][2]<edg[b][2];}
void DFS(cs u,cs fa){
anc[u][0]=fa,dep[u]=dep[fa]+1;
for(int i=1;i<20;i++) anc[u][i]=anc[anc[u][i-1]][i-1];
for(int it=Gr[u];it;it=Gr.nxt[it]){
int v=Gr.to[it];
if(v==fa) continue;
DFS(v,u);
}
}
int LCA(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;i>=0;i--)
if(dep[anc[u][i]]>=dep[v])
u=anc[u][i];
if(u==v) return u;
for(int i=19;i>=0;i--)
if(anc[u][i]!=anc[v][i])
u=anc[u][i],v=anc[v][i];
return anc[u][0];
}
void Mark(int u,int v,int len){
int lca=LCA(u,v);
while(true){
u=Ds.Find(u);
if(dep[u]<=dep[lca]) break;
tag[u]=len;
Ds.Merge(u,anc[u][0]);
}
while(true){
v=Ds.Find(v);
if(dep[v]<=dep[lca]) break;
tag[v]=len;
Ds.Merge(v,anc[v][0]);
}
}
int main(){
n=Read(),m=Read();
Ds.Init(n);
for(int i=1;i<=m;i++){
for(int j=0;j<3;j++)
edg[i][j]=Read();
id[i]=i;
}
sort(id+1,id+1+m,cmp);
int ecnt=0;
for(int I=1;I<=m;I++){
int i=id[I];
if(Ds.Merge(edg[i][0],edg[i][1])){
org+=edg[i][2];
Gr.AddEdge(edg[i][0],edg[i][1]);
del[i]=true;
ecnt++;
}
}
DFS(1,0);
Ds.Init(n);
memset(tag,-1,sizeof tag);
for(int I=1;I<=m;I++){
int i=id[I];
if(del[i]) continue;
Mark(edg[i][0],edg[i][1],edg[i][2]);
}
int q=Read();
while(q--){
int i=Read(),p;
if(ecnt<n-1){
printf("Not connected\n");
continue;
}
if(!del[i]) printf("%d\n",org);
else{
if(dep[edg[i][0]]<dep[edg[i][1]]) p=edg[i][1];
else p=edg[i][0];
if(~tag[p]) printf("%d\n",org-edg[i][2]+tag[p]);
else printf("Not connected\n");
}
}
return 0;
}

THE END

Thanks for reading!

> Linked OI Diary-Madia Lemon-Bilibili