P10928 走廊泼水节(最小生成树 贪心 并查集)

P10928 走廊泼水节

时间限制: 1.00s 内存限制: 512.00MB

复制 Markdown 退出 IDE 模式

题目描述

给定一棵 N 个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。

求增加的边的权值总和最小是多少。

注意：树中的所有边权均为整数，且新加的所有边权也必须为整数。

输入格式

第一行包含整数 t，表示共有 t 组测试数据。

对于每组测试数据，第一行包含整数 N。

接下来 N−1 行，每行三个整数 X,Y,Z，表示 X 节点与 Y 节点之间存在一条边，长度为 Z。

输出格式

每组数据输出一个整数，表示权值总和最小值。

每个结果占一行。

输入输出样例

输入 #1复制运行

2 3 1 2 2 1 3 3 4 1 2 3 2 3 4 3 4 5

输出 #1复制运行

4 17

说明/提示

数据保证，1≤t≤10，1≤N≤6000，1≤Z≤100。

根据题意 我们要保证最小生成树不变 那么我们可以先模拟一遍最小生成树的过程 当增加一条边的时候 就有两颗树合并到一起 将边权从小到大排序后 那么对于这条边的边权z 和两边树的大小s[x] s[y] 我们在每个集合中任意选择一个点 构成一条边 由于两个集合因为边z 已经合并 那么在这两个集合中选择的边不会被接下来考虑 因为这两个点已经进入了并查集 那么这条边最小就可以设置为 z+1 边的数量就是两侧集合的点的数量的乘积-1 也就是s[x]*s[y]-1 最后累加即可得到答案

代码实现如下

#include <bits/stdc++.h> using namespace std; const int N=6005; struct node{ //存边 int x,y,z; }edge[N]; int fa[N],s[N]; bool cmp(node a,node b){ //边排序 return a.z<b.z; } int get(int x){ //并查集查询 if(x==fa[x])return x; return fa[x]=get(fa[x]); } void solve(){ int n;cin>>n; for(int i=1;i<n;i++){ cin>>edge[i].x>>edge[i].y>>edge[i].z; } sort(edge+1,edge+n,cmp); for(int i=1;i<=n;i++)fa[i]=i,s[i]=1; //初始化并查集 并且维护森林中每颗树（每个集合）的大小 long long ans=0; for(int i=1;i<n;i++){ int x=get(edge[i].x); int y=get(edge[i].y); if(x==y)continue; //判断是否已经在一个并查集中 ans+=(1LL*(edge[i].z+1)*(s[x]*s[y]-1)); fa[x]=y; s[y]+=s[x]; } cout<<ans<<'\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t;cin>>t; while(t--)solve(); return 0; }