## 复试训练——图论—— 最小生成树（MST） 原

wudangt

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。

对每个测试用例，在1行里输出最小的公路总长度。

```3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0```

```3
5```

2006年浙江大学计算机及软件工程研究生机试真题

``````#include <stdio.h>
#include <algorithm>
using namespace std;
#define N 101
int Tree[N];
int findRoot(int x){
if(Tree[x]==-1) return x;
else{
int tmp=findRoot(Tree[x]);
Tree[x]=tmp;
return tmp;
}
}
struct Edge{
int a,b;
int cost;
bool operator < (const Edge &A) const{
return cost<A.cost;
}
}edge[6000];
int main(){
int n;
while(scanf("%d",&n)!=EOF&&n!=0){
int i;
for(i=1;i<=n*(n-1)/2;i++){
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost);
}
sort(edge+1,edge+1+n*(n-1)/2);
for(i=1;i<=n;i++){
Tree[i]=-1;
}
int ans=0;
for(i=1;i<n*(n-1)/2;i++){
int a=findRoot(edge[i].a);
int b=findRoot(edge[i].b);
if(a!=b){
Tree[a]=b;
ans+=edge[i].cost;
}
}
printf("%d\n",ans);
}
return 0;
}``````

In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through.
Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle.

The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle.

Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.

```3
1.0 1.0
2.0 2.0
2.0 4.0```

`3.41`

2009年北京大学计算机研究生机试真题

``````#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define N 101
int Tree[N];
int findRoot(int x){
if(Tree[x]==-1){
return x;
}else{
int tmp=findRoot(Tree[x]);
Tree[x]=tmp;
return tmp;
}
}
struct Edge{
int a,b;
double cost;
bool operator <(const  Edge &A)const{
return cost<A.cost;
}
}edge[6000];
struct Point {
double x,y;
double getDistance(Point A){
double tmp=(x-A.x)*(x-A.x)+(y-A.y)*(y-A.y);
return sqrt(tmp);
}
}list[101];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
int i;
for(i=1;i<=n;i++){
scanf("%lf%lf",&list[i].x,&list[i].y);
}
int size=0;
for(i=1;i<=n;i++){
int j;
for(j=i+1;j<=n;j++){
edge[size].a=i;
edge[size].b=j;
edge[size].cost=list[i].getDistance(list[j]);
size++;
}
}
sort(edge,edge+size);
for(i=1;i<=n;i++){
Tree[i]=-1;
}
double ans=0;
for(i=0;i<size;i++){
int a=findRoot(edge[i].a);
int b=findRoot(edge[i].b);
if(a!=b){
Tree[a]=b;
ans+=edge[i].cost;
}
}
printf("%.2lf\n",ans);
}
return 0;
}``````

### wudangt

POJ 1258 Agri-Net(Prim求最小生成树)

0 4 9 214 0 8 179 8 0 1621 17 16 0 28 Source Sample Output [Submit] [Go Back] [Status] [Discuss] 最小生成树——Minimum Spanning Tree，是图论中比较重要的模型，通常用于解决实际生活......

fire_to_cheat_
2018/03/07
0
0

cassiepython
2017/03/04
0
0
Codeforces 892E - Envy 【最小生成树】

E. Envy time limit per test 2 seconds memory limit per test 256 megabytes For a connected undirected weighted graph G, MST (minimumspanning tree) is a subgraph of G that contain......

my_sunshine26
2017/12/19
0
0
CCNP笔记——MST上

CCNP笔记--MSTP上 第一次看CCNP学习指南时，对书中描述MST的部分简直一头雾水，有种受挫的感觉。后来通过实验并结合书中的内容才对MST有了初步的了解。下面通过实验说明自己对MSTP的认识： ...

taolinba213
2016/07/18
0
0
SDUT-图结构练习——最小生成树

wzy_2017
2017/06/07
0
0

nginx学习笔记

5
0
Spring Security 实战干货：玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战，如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证（Authentication），认证...

9
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie

12
0
PhotoShop 色调：RGB／CMYK 颜色模式

11
1

13
0