hdu Eddy's picture （最小生成树）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1162


/************************************************************************/
/*     
        hdu  Eddy's picture
        最小生成树
        题目大意：在坐标轴上存在n个点，求这n个点组成的最小图，使得图的总路径最短
        解题思路：求最小生成树
*/
/************************************************************************/

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

typedef struct 
{
    double x;
    double y;
}P;

const int N = 101;
P p[N];
double map[N][N];
int mark[N];
int n,q,i,j;

//返回两个点的距离
double distance(P p1,P p2)
{
    return sqrt(pow(p1.x - p2.x,2)+pow(p1.y-p2.y,2));
}

double Prim()
{
    double sum = 0;
    memset(mark,0,sizeof(mark));
    int k,t = n;
    while(--t)
    {
        double min = 100000;
        for (i = 1; i < n; i++)
        {
            if(mark[i] != 1 && min > map[0][i])
            {
                min = map[0][i];
                k = i;
            }
        }
        mark[k] = 1;
        sum += min;
        for( j = 1; j < n; j++)
        {
            if(mark[j]!=1 && map[k][j] < map[0][j])
                map[0][j] = map[k][j];
        }
    }
    return sum;
}


int main()
{
    while(scanf("%d",&n) != EOF)
    {
        for(i = 0; i < n; i++)
        {
            scanf("%lf%lf",&(p[i].x),&(p[i].y));
        }
        for (i = 0; i < n; i++)
        {
            for(j = i; j < n; j++)
            {
                if(i==j) map[i][j] = map[j][i] = 0;
                else map[i][j] = map[j][i] = distance(p[i],p[j]);
            }
        }
        printf("%.2f\n",Prim());
    }
    
    return 0;
}