NOIP2023模拟5联测26 零

本文主要是介绍NOIP2023模拟5联测26 零，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

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

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

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

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

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

题解

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

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

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

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

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

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

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

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

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

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

code

#include<bits/stdc++.h>
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;
}