Vijos1579 宿命的PSS 题解

CSDN同步

原题链接

简要题意：

给定一棵树，求 边权的最小的完全图，使得该完全图的最小生成树为给定的树。

首先，我们回忆一下：求 最小生成树 不外乎两个算法：

• \(\texttt{prim}\)
• \(\texttt{kruskal}\)

它们都是基于贪心的一种算法（只不过选边顺序略区别）。

按照它们的思想来说，每次选一个边权最小的端点属于不同连通块的连接，用并查集维护连通块 即可完成。（\(\texttt{kruskal}\) 算法）

那么，已知了最小生成树：

因为每两个顶点都有边（完全图 的定义），所以应当尽量让 新加的边与已知边接近但不低于（也不等于）当前边。

比方说样例：

那么，如果 \(1 \rightarrow 3\) 这条边 \(\leq 7\)，那么，\(2 \rightarrow 3\) 就可以被它替换，所以，\(1 \rightarrow 3\) 这条边只能是 \(\geq 7+1\)，\(\therefore\) 答案为 \(7+4+8 = 19\).

所以，对于 \(x\) 和 \(y\) 的这条边维护它们当前被连边的个数。（初始为 \(1\)）然后排序统计，维护并查集完事！

时间复杂度：\(O(n+m)\).（并查集的常数 \(\alpha \leq 4\) 仍然被我忽略）

实际得分：\(100pts\).

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+1;
typedef long long ll;

inline int read(){char ch=getchar();int f=1;while(ch<‘0‘ || ch>‘9‘) {if(ch==‘-‘) f=-f; ch=getchar();}
	int x=0;while(ch>=‘0‘ && ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x*f;}

struct node {
	int u,v,w;
}; node G[N];
int f[N],n;
ll ans=0,d[N];

inline bool cmp(node x,node y) {
	return x.w<y.w;
}

inline int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}

int main(){
	n=read();
	for(int i=1;i<=n;i++) {
		f[i]=i; d[i]=1;
		if(i!=n) G[i].u=read(),G[i].v=read(),G[i].w=read();
	} sort(G+1,G+n,cmp);
	for(int i=1;i<n;i++) {
		int x=find(G[i].u),y=find(G[i].v);
		ans+=G[i].w+(G[i].w+1)*(d[x]*d[y]-1);
		d[y]+=d[x]; f[x]=y;
	} 
//    for(int i=1;i<=n;i++) printf("%d ",d[i]); putchar(‘\n‘);
//    for(int i=1;i<=n;i++) printf("%d ",f[i]); putchar(‘\n‘);
	printf("%lld\n",ans);
	return 0;
}

Vijos1579 宿命的PSS 题解

原文：https://www.cnblogs.com/bifanwen/p/12631883.html