NOIP2023模拟5联测26 零

题目大意

完全无向图是指任意一对顶点间都有边连接的简单无向图，$n$个结点的完全无向图有$M=\frac{n(n-1)}{2}$条边。

如果有一个有$n$个结点的带权完全无向图，$M$条边的权值是$1$到$M$的一个排列，则这张图是合法的。

现在给定一个有$n$个结点$m$条边的带权无向连通图，边权为$1$到$M$中两两不等的整数，你需要添加$M-m$条边，使得这张图是合法的，且加边前后最小生成树的权值和不变。

问是否存在至少一种满足要求的加边方案。

$1\le n,m\le 5\times 10^5$

题解

我们可以用$Kruskal$的思想，将所有边从小到大排序，来构成最小生成树。如果当前边的两个端点不连通，那么将两个点所在的连通块用并查集合起来，这条边就是树边。我们发现，如果要加一条连接$x,y$的边，则要满足边权$w$大于这两个点在树上的路径上的每条边的边权。换句话说，如果要加一条连接$x,y$的边，那么在做$Kruskal$的时候，做完边权小于$w$的边之后$x,y$要在同一个连通块中。

也就是说，如果当前连的是边权为$w$的树边，则这条树边所在的连通块内任意两个点都可以加一条边权大于$w$的边。

那么，我们在做并查集的时候，每次将两个连通块$a$和$b$合并后，可以加边的点对的数量就增加了$si{z}_a\times si{z}_b-1$个（其中$si{z}_a$和$si{z}_b$分别表示在合并前连通块$a$和$b$中点的数量，这其实就是在$a$和$b$各选一个点来作为加的边的端点，减一是因为将两个连通块连接的那条边是原来就有的边，不能算作可以被加的边）。

那么， 我们用$now$记录在做$Kruskal$的过程中到目前为止还剩的可以加的边，每次连完一条树边$i$，设上一条连的树边为$j$，则这两条树边之间有$w_i-w_j+1$个权值没有被加，那么$now$的值就减去$w_i-w_j+1$。如果在过程中出现$now<0$的情况，则输出$No$；否则，输出$Yes$。

不过，这样做还是有问题的。在做并查集求增加的可以加边的点对的数量时，可能有一些边是题目中已经连接的，只是不在最小生成树上，这类边是不能看作可以加的边的。也就是说，我们要想一种办法，让这种边不算在可以加的边中。

对于每条题目中已经连接但不在最小生成树上的边$t$，我们考虑求边权最小的一条边$i$，使得在加了这条边之后，边$t$的两个端点连通，此时在加上$si{z}_a\times si{z}_b-1$之后，还要在减去边$t$的贡献。

我们发现，因为树边是从小到大连接的，所以上面的边$i$其实就是边$t$的两个端点$x,y$在树上的路径中边权最大的边，我们用倍增来求边$i$即可。

我们用$su{m}_i$表示每个树边$i$来记录每次将$i$的两个端点所在的连通块连通之后多算的可以加边的点对，那么对于每个$t$求出$i$之后，令$su{m}_i=su{m}_i+1$即可。

注意在计算可以加的边的权值时，题目已经连接但不在最小生成树中的边不需要算入其中。

时间复杂度为$O(n\log n)$。

code

#include
using namespace std;
const int N=500000;
int n,m,tot=0,d[2*N+5],l[2*N+5],r[N+5],id[2*N+5],fa[N+5],siz[N+5];
int dep[N+5],f[N+5][20],g[N+5][20];
long long nd=0,now=0,sum[N+5];
struct node{
	int x,y,z;
	long long w;
}w[N+5];
bool cmp(node ax,node bx){
	return ax.w<bx.w;
}
void add(int xx,int yy,int i){
	l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;id[tot]=i;
}
int find(int ff){
	if(fa[ff]!=ff) fa[ff]=find(fa[ff]);
	return fa[ff];
}
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	for(int i=1;i<=19;i++){
		int y=f[u][i-1];
		f[u][i]=f[y][i-1];
		if(w[g[u][i-1]].w>w[g[y][i-1]].w) g[u][i]=g[u][i-1];
		else g[u][i]=g[y][i-1];
	}
	for(int i=r[u];i;i=l[i]){
		if(d[i]==fa) continue;
		f[d[i]][0]=u;
		g[d[i]][0]=id[i];
		dfs(d[i],u);
	}
}
int gt(int x,int y){
	int re=0;
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;i--){
		if(dep[f[x][i]]>=dep[y]){
			if(w[g[x][i]].w>w[re].w) re=g[x][i];
			x=f[x][i];
		}
	}
	if(x==y) return re;
	for(int i=19;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			if(w[g[x][i]].w>w[re].w) re=g[x][i];
			if(w[g[y][i]].w>w[re].w) re=g[y][i];
			x=f[x][i];y=f[y][i];
		}
	}
	if(w[g[x][0]].w>w[re].w) re=g[x][0];
	if(w[g[y][0]].w>w[re].w) re=g[y][0];
	return re;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%lld",&w[i].x,&w[i].y,&w[i].w);
	}
	sort(w+1,w+m+1,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int v1=find(w[i].x),v2=find(w[i].y);
		if(v1!=v2){
			fa[v1]=v2;
			w[i].z=1;
			add(w[i].x,w[i].y,i);
			add(w[i].y,w[i].x,i);
		}
	}
	dfs(1,0);
	for(int i=1;i<=m;i++){
		if(!w[i].z){
			++sum[gt(w[i].x,w[i].y)];
		}
	}
	for(int i=1;i<=n;i++){
		fa[i]=i;siz[i]=1;
	}
	for(int i=1;i<=m;i++){
		nd+=w[i].w-w[i-1].w-1;
		if(w[i].z){
			int v1=find(w[i].x),v2=find(w[i].y);
			now-=nd;nd=0;
			if(now<0){
				printf("No");
				return 0;
			}
			now+=1ll*siz[v2]*siz[v1]-1;
			now-=sum[i];
			fa[v1]=v2;
			siz[v2]+=siz[v1];
		}
	}
	printf("Yes");
	return 0;
}
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