当前位置:网站首页>AcWing 346. Solution to the problem of water splashing festival in the corridor (deduction formula, minimum spanning tree)
AcWing 346. Solution to the problem of water splashing festival in the corridor (deduction formula, minimum spanning tree)
2022-07-07 01:36:00 【Mr. Qiao Da】
AcWing 346. Corridor Water Splashing Festival
The key to solving the problem is to deduce the formula :**(Size[a] * Size[b] - 1) * (w + 1)** The meaning of this formula is mortgage : Traverse to two points belonging to two different connected blocks connected by a certain edge , Connect all points of the two connecting blocks to each other , Subtract an existing edge , After introducing the formula , Traverse all edges according to the algorithm of minimum spanning tree , Find out two points that are not in a connected block and accumulate the calculated value with a formula
#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};
}
// Initialize and query array
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); // The formula , Connect all points of the two connecting blocks to each other , Subtract an existing edge
p[a] = b;
Size[b] += Size[a];
}
}
cout<<res<<endl;
}
return 0;
}
边栏推荐
- tansig和logsig的差异,为什么BP喜欢用tansig
- Go zero micro service practical series (IX. ultimate optimization of seckill performance)
- 736. Lisp 语法解析 : DFS 模拟题
- Docker method to install MySQL
- Dark horse notes - exception handling
- Neon Optimization: an optimization case of log10 function
- c语言—数组
- C language instance_ four
- mongodb查看表是否导入成功
- Add the applet "lazycodeloading": "requiredcomponents" in taro,
猜你喜欢
随机推荐
从底层结构开始学习FPGA----FIFO IP的定制与测试
736. LISP syntax parsing: DFS simulation questions
7.6 simulation summary
Asset security issues or constraints on the development of the encryption industry, risk control + compliance has become the key to breaking the platform
THREE. AxesHelper is not a constructor
Let's see through the network i/o model from beginning to end
mysqlbackup 还原特定的表
1123. 最深叶节点的最近公共祖先
Comparison of picture beds of free white whoring
AcWing 346. 走廊泼水节 题解(推公式、最小生成树)
交叉验证如何防止过拟合
Receive user input, height BMI, BMI detection small business entry case
剑指 Offer II 035. 最小时间差-快速排序加数据转换
域分析工具BloodHound的使用说明
今日问题-2022/7/4 lambda体中修改String引用类型变量
tansig和logsig的差异,为什么BP喜欢用tansig
从零开始匹配vim(0)——vimscript 简介
Make Jar, Not War
[advanced C language] 8 written questions of pointer
Today's question -2022/7/4 modify string reference type variables in lambda body