当前位置:网站首页>AcWing 346. 走廊泼水节 题解(推公式、最小生成树)
AcWing 346. 走廊泼水节 题解(推公式、最小生成树)
2022-07-06 18:00:00 【乔大先生】
AcWing 346. 走廊泼水节
解题关键在于推出公式:**(Size[a] * Size[b] - 1) * (w + 1)**这个公式的意义按揭的:遍历到某条边连接的属于两个不同的连通块的两个点,将两个联通块的所有点互相连接,减去已经存在的一条边 ,推出公式后,按照最小生成树的算法遍历所有边,找出不在一个连通块的两个点用公式累加计算值
#include<bits/stdc++.h>
using namespace std;
const int N = 6010;
struct Edge{
int a, b, w;
bool operator< (const Edge &t) const {
return w < t.w;
}
}e[N * 4];
int T, n, m;
int p[N];
int Size[N];
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin>>T;
while(T -- ){
cin>>n;
int res = 0;
for(int i = 0; i < n - 1; i ++ ){
int a, b, w;
cin>>a>>b>>w;
e[i] = {
a, b, w};
}
//初始化并查集数组
for(int i = 1; i <= n; i ++ ){
p[i] = i;
Size[i] = 1;
}
sort(e, e + n - 1);
for(int i = 0; i < n - 1; i ++ ){
int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
if(a != b){
res += (Size[a] * Size[b] - 1) * (w + 1); //公式,将两个联通块的所有点互相连接,减去已经存在的一条边
p[a] = b;
Size[b] += Size[a];
}
}
cout<<res<<endl;
}
return 0;
}
边栏推荐
- 力扣1037. 有效的回旋镖
- Transformation transformation operator
- How to prevent overfitting in cross validation
- 编译命令行终端 swift
- 子网划分、构造超网 典型题
- JTAG debugging experience of arm bare board debugging
- 如何管理分布式团队?
- Neon Optimization: summary of performance optimization experience
- THREE. AxesHelper is not a constructor
- C language instance_ three
猜你喜欢
Yunna - work order management system and process, work order management specification
LeetCode. 剑指offer 62. 圆圈中最后剩下的数
力扣1037. 有效的回旋镖
How to manage distributed teams?
黑马笔记---创建不可变集合与Stream流
[100 cases of JVM tuning practice] 05 - Method area tuning practice (Part 2)
云呐-工单管理制度及流程,工单管理规范
Let's see through the network i/o model from beginning to end
修改px4飞控的系统时间
C language - array
随机推荐
Byte P7 professional level explanation: common tools and test methods for interface testing, Freeman
Metauniverse urban legend 02: metaphor of the number one player
Vocabulary in Data Book
Meet in the middle
Analysis of mutex principle in golang
Start from the bottom structure to learn the customization and testing of fpga---- FIFO IP
子网划分、构造超网 典型题
[case sharing] basic function configuration of network loop detection
Go zero micro service practical series (IX. ultimate optimization of seckill performance)
Spark TPCDS Data Gen
分享一个通用的so动态库的编译方法
Yunna - work order management system and process, work order management specification
Oracle: Practice of CDB restricting PDB resources
golang中的atomic,以及CAS操作
The cost of returning tables in MySQL
HMM 笔记
编译命令行终端 swift
Add the applet "lazycodeloading": "requiredcomponents" in taro,
Neon Optimization: performance optimization FAQ QA
安利一波C2工具