算法竞赛进阶指南 走廊泼水节

标签：怎么办   要求   code   格式   i++   描述   顺序   输入格式   find   

原题链接

题目描述

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

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

输入格式

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

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

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

输出格式

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

每个结果占一行。

数据范围

\(N \le 6000,Z \le 100\)

输入样例：

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

输出样例：

4
17 

解题报告

题意理解

这道题目说的很清楚,就是让我们将一个最小生成树的图,添加一些边,使得这张图成为一个完全图.

但是我们这张图的最小生成树,必须还是原来那张图的最小生成树.

也就是说两张图的最小生成树表示是一模一样的.

算法解析

根据上面的信息,我们不难发现这道题目和最小生成树算法联系紧密,那么现在我们的主要问题就在于如何去构造最小生成树.

我们可以考虑最小生成树算法中的Kruskal算法.

1. 首先将所有的边按照从小到大的顺序排序.

此时我们保证了是最小生成树的完美生成法则.

1. 对于每一条边\((x,y,w)\)而言,他们之间有某种关系.

假如说\(x\)和\(y\)不在同一个连通块(集合)之中,也就是他们之间没有边相连

那么我们相连之后,现在这两个点,各自所在的连通块(集合),都拥有了一个最短边,也就是\((x,y,w)\).

最小生成树是已经确定了,但是对于这原来两个连通块的其他点怎么办?
\[ 首先我们设S_x表示为x之前所在的连通块 \那么S_y表示为y之前所在的连通块. \]
因为我们不能破坏这个最小生成树,所以我们这原来的两个连通块中的点就必须有如下性质.
\[ 假如说点A属于S_x这个集合之中 \点B属于S_y这个集合之中. \]
那么点\(A\)与点\(B\)之间的距离,必须要大于之前的\(w\),否则就会破坏之前的最小生成树
\[ 所以说(A,B)之间的距离最小为w+1 \]

假如说我们知道
\[ S_x有p个元素,然后S_y有q个元素. \]
那么将
\[ S_x与S_y连通块的所有点相连. \]
显然这个两个连通块会增加.
\[ p \times q-1条边 \]
然后每一条边的最小长度为
\[ w+1 \]
所以我们会得出
\[ (w+1) \times (p*q-1)为两个连通块成为完全图的最小代价 \]

代码解析

#include 
using namespace std;
const int N=1e4+100;
int fa[N],n,m,i,j,k,t,s[N];
long long ans;
struct node
{
    int x,y,w;
} edge[N];
bool cmp(node a,node b)
{
    return a.w

算法竞赛进阶指南 走廊泼水节

标签：怎么办   要求   code   格式   i++   描述   顺序   输入格式   find   

原文地址：https://www.cnblogs.com/gzh-red/p/11013114.html