题目1017：还是畅通工程

题目描述：

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

输入：

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

输出：

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

样例输入：

31 2 11 3 22 3 441 2 11 3 41 4 12 3 32 4 23 4 50

样例输出：

35

来源：

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\n",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.

样例输入：

31.0 1.02.0 2.02.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\n",sum);    }    return 0;} /**************************************************************    Problem: 1144    User: lcyvino    Language: C++    Result: Accepted    Time:330 ms    Memory:1616 kb****************************************************************/

 

关于【最小生成树】