ZOJ 1203 Swordfish （經典MST ~ Kruscal）Boruvka算法

連結：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=203

Description： 

We all remember that in the movie Swordfish, Gabriel broke into the World Bank Investors Group in West Los Angeles, to rob $9.5 billion. And he needed Stanley, the best hacker in the world, to help him break into the password protecting the bank system. Stanley's lovely daughter Holly was seized by Gabriel, so he had to work for him. But at the last moment, Stanley made some little trick in his hacker mission: he injected a trojan horse in the bank system, so the money would jump from one account to another account every 60 seconds, and would continue jumping in the next 10 years. Only Stanley knew when and where to get the money. If Gabriel killed Stanley, he would never get a single dollar. Stanley wanted Gabriel to release all these hostages and he would help him to find the money back.

  You who has watched the movie know that Gabriel at last got the money by threatening to hang Ginger to death. Why not Gabriel go get the money himself? Because these money keep jumping, and these accounts are scattered in different cities. In order to gather up these money Gabriel would need to build money transfering tunnels to connect all these cities. Surely it will be really expensive to construct such a transfering tunnel, so Gabriel wants to find out the minimal total length of the tunnel required to connect all these cites. Now he asks you to write a computer program to find out the minimal length. Since Gabriel will get caught at the end of it anyway, so you can go ahead and write the program without feeling guilty about helping a criminal.

Input:

The input contains several test cases. Each test case begins with a line contains only one integer N (0 <= N <=100), which indicates the number of cities you have to connect. The next N lines each contains two real numbers X and Y(-10000 <= X,Y <= 10000), which are the citie's Cartesian coordinates (to make the problem simple, we can assume that we live in a flat world). The input is terminated by a case with N=0 and you must not print any output for this case.

Output:

You need to help Gabriel calculate the minimal length of tunnel needed to connect all these cites. You can saftly assume that such a tunnel can be built directly from one city to another. For each of the input cases, the output shall consist of two lines: the first line contains "Case #n:", where n is the case number (starting from 1); and the next line contains "The minimal distance is: d", where d is the minimal distance, rounded to 2 decimal places. Output a blank line between two test cases.

Sample Input:

5
0 0
0 1
1 1
1 0
0.5 0.5
0
      

Sample Output:

Case #1:
The minimal distance is: 2.83      

分析：

1. 對圖中各頂點，将與其關聯，具有最小權邊的邊選入MST，得到由MST子樹構成的森林；

2. 在圖中陸續選擇可以連接配接兩顆不同子樹且具有最小權值的邊，将子樹合并，最終構造成MST；

代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <cmath>
#define MAXN 105  //頂點個數的最大值；
#define MAXM 5005  //邊的個數的最大值；
#include <algorithm>
#define INF 0x1f1f1f1f
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

struct Edge
{
    int u, v;   //邊的頂點；
    double w;   //邊的權值；
}edge[MAXM];

int parent[MAXN], n, m, cas = 1;  //每個頂點對應的父親節點， 頂點個數，邊個數，測試資料個數；
double X[MAXN], Y[MAXN], res;     //每個頂點的X坐标和Y坐标；生成樹的權值；

double Mul(double x) { return (double)x*x; }

void Init()
{
    for(int i=0; i<n; i++) scanf("%lf %lf", &X[i], &Y[i]);   //讀入頂點個數；
    int k = 0;
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            double dist = sqrt(Mul(X[i]-X[j]) + Mul(Y[i]-Y[j]));
            edge[k].u = i, edge[k].v = j, edge[k++].w = dist;
        }
    }
    m = k;
}

void Make_Set()    //初始化每個節點；
{
    for(int i=0; i<n; i++) {
        parent[i] = -1;
    }
}

int Find(int x)    //查找父親節點；
{
    int s;
    for(s=x; parent[s]>=0; s=parent[s]);
    while(s != x) {
        int temp = parent[x];
        parent[x] = s;
        x = temp;
    }
    return s;
}

void Union_Set(int x, int y)   //節點合并；
{
    x = Find(x), y = Find(y);
    int temp = parent[x] + parent[y];
    if(parent[x] > parent[y]) {
        parent[x] = y;
        parent[y] = temp;
    }else {
        parent[y] = x;
        parent[x] = temp;
    }
}

int cmp(const void *a, const void *b)  //按邊從小到大進行排序；
{
    Edge p1 = *(const Edge *)a;
    Edge p2 = *(const Edge *)b;
    if(p1.w > p2.w) return 1;
    else return -1;
}

void Kruscal()    //Kruscal 算法；
{ 
    int cnt = 0, Mc, Md;
    Make_Set();
    for(int i=0; i<m; i++) {
        Mc = edge[i].u, Md = edge[i].v;
        if(Find(Mc) != Find(Md)) {
            res += edge[i].w, cnt++;
            Union_Set(Mc, Md);
        }
        if(cnt >= n-1) break;
    }
}

int main()
{
    while(~scanf("%d", &n) && n) {
        Init();
        qsort(edge, m, sizeof(Edge), cmp);
        res = 0.0;    
        Kruscal();
        if(cas > 1) printf("\n");
        printf("Case #%d:\n", cas++);
        printf("The minimal distance is: %.2lf\n", res);
    }
    return 0;
}