关于【最小生成树】

题目1017：还是畅通工程

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

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

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

样例输入：

样例输出：

3
5

来源：

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

代码如下：

#include <iostream>
#include <stdio.h>
 
using namespace std;
 
struct Edge{
    int a;
    int b;
    int cost;
}edge[6000];
 
int findRoot(int Tree[],int x){
    if(Tree[x]==-1)
        return x;
    else{
        int temp=findRoot(Tree,Tree[x]);
        Tree[x]=temp;
        return temp;
    }
}
 
void sortEdge(Edge edge[],int n){
    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++){
            if(edge[i].cost>edge[j].cost){
                Edge temp;
                temp.a=edge[i].a;
                temp.b=edge[i].b;
                temp.cost=edge[i].cost;
                edge[i].a=edge[j].a;
                edge[i].b=edge[j].b;
                edge[i].cost=edge[j].cost;
                edge[j].a=temp.a;
                edge[j].b=temp.b;
                edge[j].cost=temp.cost;
            }
        }
    }
}
 
int main()
{
    int N;
    int Tree[100];
    while(scanf("%d",&N)!=EOF&&N!=0){
        for(int i=1;i<=N*(N-1)/2;i++){
            scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost);
        }
        sortEdge(edge,N*(N-1)/2);
        for(int i=1;i<=N;i++)
            Tree[i]=-1;
        int sum=0;
        for(int i=1;i<=N*(N-1)/2;i++){
            int root_a=findRoot(Tree,edge[i].a);
            int root_b=findRoot(Tree,edge[i].b);
            if(root_a!=root_b){
                Tree[root_b]=root_a;
                sum+=edge[i].cost;
            }
        }
        printf("%d
",sum);
    }
    return 0;
}
 
/**************************************************************
    Problem: 1017
    User: lcyvino
    Language: C++
    Result: Accepted
    Time:80 ms
    Memory:1588 kb
****************************************************************/

题目1144：Freckles

题目描述：: 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 <iostream>
#include <stdio.h>
#include <math.h>
 
using namespace std;
 
struct point{
    double x;
    double y;
}buf[101];    //记录输入的结点信息
 
struct Edge{
    int a;
    int b;
    double cost;
}edge[6000];  //记录边的信息
 
double getDistance(point A,point B){    //计算2点之间的距离
    double temp=(A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
    return sqrt(temp);
}
 
int findRoot(int Tree[],int x){   //寻找结点的根结点
    if(Tree[x]==-1)
        return x;
    else{
        int temp=findRoot(Tree,Tree[x]);
        Tree[x]=temp;
        return temp;
    }
}
 
void sortEdge(Edge edge[],int n){  //对生成的边按照权值的从小到大进行排序
    for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++){
            if(edge[i].cost>edge[j].cost){    //很傻逼的交换
                Edge temp;
                temp.a=edge[i].a;
                temp.b=edge[i].b;
                temp.cost=edge[i].cost;
                edge[i].a=edge[j].a;
                edge[i].b=edge[j].b;
                edge[i].cost=edge[j].cost;
                edge[j].a=temp.a;
                edge[j].b=temp.b;
                edge[j].cost=temp.cost;
            }
        }
    }
}
 
int main()
{
    int n;
    int Tree[101];   //用于记录每个点的双亲结点
    while(scanf("%d",&n)!=EOF&&n!=0){
        for(int i=1;i<=n;i++){
            scanf("%lf%lf",&buf[i].x,&buf[i].y);  //输入坐标的信息，存储在buf数组内
        }
        for(int i=1;i<=n;i++){   //类似于初始化，把每个点的双亲结点置为-1
            Tree[i]=-1;
        }
        int loc=1;//用于记录边的条数
        for(int i=1;i<=n-1;i++){      //开始计算每条边的信息，包括边两端相连的结点
            for(int j=i+1;j<=n;j++){  //还有边的权值
                edge[loc].a=i;
                edge[loc].b=j;
                edge[loc].cost=getDistance(buf[i],buf[j]);
                loc++;
            }
        }
        loc--;                      //一共有多少条边
        sortEdge(edge,loc);
        double sum=0;               //算总的权值大小
        for(int i=1;i<=loc;i++){
            int root_a=findRoot(Tree,edge[i].a);
            int root_b=findRoot(Tree,edge[i].b);
            if(root_a!=root_b){             //如果两个点不属于一个集合，那么连接这两个坐标的边
                Tree[root_b]=root_a;        //可以作为最小生成树里的 一条边
                sum+=edge[i].cost;
            }
        }
        printf("%.2lf
",sum);
    }
    return 0;
}
 
/**************************************************************
    Problem: 1144
    User: lcyvino
    Language: C++
    Result: Accepted
    Time:330 ms
    Memory:1616 kb
****************************************************************/

题目1028：继续畅通工程

题目描述：: 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。

输入：: 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

当N为0时输入结束。

输出：: 每个测试用例的输出占一行，输出全省畅通需要的最低成本。

样例输入：

样例输出：

3
1
0

来源：

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

代码如下：

#include <iostream>
#include <stdio.h>
 
using namespace std;
 
struct Edge{   //定义边
    int head;
    int tail;
    int cost;
    int flag;
}edge[6000];
 
int findRoot(int Tree[],int x){
    if(Tree[x]==-1)
        return x;
    else{
        int temp=findRoot(Tree,Tree[x]);
        Tree[x]=temp;
        return temp;
    }
}
 
void sortEdge(Edge edge[],int N){
    for(int i=1;i<=N*(N-1)/2-1;i++){
        for(int j=i+1;j<=N*(N-1)/2;j++){
            if(edge[i].cost>=edge[j].cost){
                Edge temp;
                temp.head=edge[i].head;
                temp.tail=edge[i].tail;
                temp.cost=edge[i].cost;
                temp.flag=edge[i].flag;
                edge[i].head=edge[j].head;
                edge[i].tail=edge[j].tail;
                edge[i].cost=edge[j].cost;
                edge[i].flag=edge[j].flag;
                edge[j].head=temp.head;
                edge[j].tail=temp.tail;
                edge[j].cost=temp.cost;
                edge[j].flag=temp.flag;
            }
        }
    }
}
 
int main()
{
    int N;
    int Tree[110];
    while(scanf("%d",&N)!=EOF&&N!=0){
        for(int i=1;i<=N;i++){
            Tree[i]=-1;
        }
        for(int i=1;i<=N*(N-1)/2;i++){
            scanf("%d%d%d%d",&edge[i].head,&edge[i].tail,&edge[i].cost,&edge[i].flag);
            if(edge[i].flag==1)     //如果道路已经修建，将它的ost置为0
                edge[i].cost=0;
        }
        sortEdge(edge,N);
        int sum=0;
        for(int i=1;i<=N*(N-1)/2;i++){
            int root_head=findRoot(Tree,edge[i].head);
            int root_tail=findRoot(Tree,edge[i].tail);
            if(root_head!=root_tail){
                Tree[root_head]=root_tail;
                sum+=edge[i].cost;
            }
        }
        printf("%d
",sum);
    }
    return 0;
}
 
/**************************************************************
    Problem: 1028
    User: lcyvino
    Language: C++
    Result: Accepted
    Time:120 ms
    Memory:1612 kb
****************************************************************/