HDU1162Eddy's picture(最小生成树)

题目链接。

解题报告：

用了两个方法。。一个是Kruskal， 一个是prim。对于本题。。还是prim写起来容易点。。

Kruskal:

prim:

。。直接上代码

Kruskal AC代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXN 100

typedef struct Pointer{
    double x, y;
}Pointer;

struct Num{
    int x, y;
    double dis;
}num[MAXN*(MAXN-1)/2];

Pointer pos[MAXN];
int n, _index, p[MAXN];

double calc(Pointer a, Pointer b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int find(int x){return p[x] == x ? x : (p[x] = find(p[x]));}

int cmp(const void *a, const void *b){
    struct Num x = *(struct Num *)a, y = *(struct Num *)b;
    return x.dis - y.dis > 0 ?  1 : -1;
}

int main(){
    int i, j;
    double ans;
    while(scanf("%d", &n) == 1){
        _index = 0;
        ans = 0.0;
        for(i=0; i<n; i++){
            scanf("%lf %lf", &pos[i].x, &pos[i].y);
        }
        for(i=0; i<n; i++){
            for(j=i+1; j<n; j++){
                num[_index].x = i; num[_index].y = j;
                num[_index++].dis = calc(pos[i], pos[j]);
            }
        }

        for(i=0; i<n; i++) p[i] = i;
        qsort(num, _index, sizeof(num[0]), cmp);
        for(i=0; i<_index; i++){
            int x = find(num[i].x), y = find(num[i].y);
            if(x != y){
                ans += num[i].dis; p[x] = y;
            }
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}

prim:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define MAXN 101

const double INF = (double)(1<<24);

typedef struct Pointer{
    double x, y;
}Pointer;

Pointer pos[MAXN];
double G[MAXN][MAXN], d[MAXN];
int v[MAXN];

double prim(int v0, int n){
    memset(v, 0, sizeof(v));
    int i, x, y;
    double ans = 0.0;
    for(i=0; i<n; i++){
        d[i] = G[v0][i];
    }
    d[v0] = 0; v[v0] = 1;
    for(i=1; i<n; i++){
        double m = INF;
        for(y=0; y<n; y++)if(!v[y] && d[y] < m) m = d[x=y];
        v[x] = 1;
        ans += m;
        for(y=0; y<n; y++)if(!v[y] && G[x][y]<d[y]){
           d[y] = G[x][y];
        }
    }
    return ans;
}

int main(){
    int n, i, j;
    while(scanf("%d", &n) == 1){
        for(i=0; i<n; i++){
            scanf("%lf %lf", &pos[i].x, &pos[i].y);
        }
        for(i=0; i<n; i++){
            for(j=0; j<=i; j++){
                if(i == j) G[i][j] = INF;
                else G[i][j] = G[j][i] =
                    sqrt((pos[i].x-pos[j].x)*(pos[i].x-pos[j].x)+(pos[i].y-pos[j].y)*(pos[i].y-pos[j].y));

            }
        }
        printf("%.2lf\n", prim(0, n));
    }


    return 0;
}