最小生成树。

CODE：

 

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <climits>    

//INT_MAX,整形范围内的最大整数。

#include <algorithm>

using 

namespace std;

#define INF 0x3f3f3f3f

const 

int SIZE = 

110;

double w[SIZE][SIZE];

double d[SIZE];

int v[SIZE];

int n;

struct node

{

    

double x, y;

}a[SIZE];

double fun(

const node a, 

const node b)

{

    

return sqrt((b.y - a.y) * (b.y - a.y) + (b.x - a.x) * (b.x - a.x));

}

double Prim(

int src)

{

    

int i, j;

    

double cnt = 

0;

    

for(i = 

1; i <= n; i++) d[i] = (i == src)? 

0:INF;

    

for(i = 

1; i <= n; i++)

    {

        

int x;

        

double m = INF;

        

for(

int y = 

1; y <= n; y++) 

if(!v[y] && m > d[y]) m = d[x=y];

        v[x] = 

1;

        cnt += m;

        

for(

int y = 

1; y <= n; y++) d[y] <?= w[x][y];

    }

    

return cnt;

}

void init()

{

    memset(v, 

0, 

sizeof(v));

    memset(d, 

0, 

sizeof(d));

    memset(a, 

0, 

sizeof(a));

    

for(

int i = 

1; i <= SIZE; i++)

        

for(

int j = 

1; j <= SIZE; j++)

            w[i][j] = INF;

}

int main()

{

    

int i, j;

    

while(~scanf(

"

%d

", &n))

    {

        init();

        

for(i = 

1; i <= n; i++)

        {

            scanf(

"

%lf%lf

", &a[i].x, &a[i].y);

        }

        

for(i = 

1; i <= n; i++)

        {

            

for(j = 

1; j <= n; j++)

            {

                

if(i == j) 

continue;

                w[i][j] = fun(a[i], a[j]);

            }

        }

        

double ans = Prim(

1);

        printf(

"

%.2lf\n

", ans);

    }

    

return 

0;

}