hdu 1162 && hdu 1875

这来到题目差不多，因为几乎是每条边都用到，所以用prim算法应该会比较好，从运行的效率来看也十分明显

hdu1875 则对边做了一定的限制，只需要的加边的时候判断一下就好了

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<math.h>
#define MAXN 101 
#define MAXINT 99999999
using namespace std;
int n,s[MAXN];
double dis[MAXN],map[MAXN][MAXN];
struct  node{
    double x,y;
}node1[MAXN];
double distance(int i,int j)
{
    return (node1[i].x-node1[j].x)*(node1[i].x-node1[j].x)+(node1[i].y-node1[j].y)*(node1[i].y-node1[j].y);
}
void prim()
{
    for(int i=1;i<=n;i++)
        dis[i]=map[1][i];
    dis[1]=0;
    memset(s,0,sizeof(s));
    s[1]=1;
    double ans=0;
    for(int i=1;i<n;i++)
    {
        int tmp=MAXINT,v=1;
        for(int j=1;j<=n;j++)
            if(!s[j]&&dis[j]<tmp)
                v=j,tmp=dis[j];
        s[v]=1;
        ans+=(double)sqrt((double)(tmp));
        for(int j=1;j<=n;j++)
        {
            tmp=map[v][j];
            if(tmp<dis[j]) dis[j]=tmp;
        }
    }
    printf("%.2f\n",ans);
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        for(int i=1;i<=n;i++)
            scanf("%lf %lf",&node1[i].x,&node1[i].y);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                map[i][j]=abs((double)distance(i,j));
        prim();
    }
    return 0;
}

　　

#include <stdio.h>
#include <limits.h>
#include <math.h>
static const int V = 100;
struct Pos
{
    int x;
    int y;
    int operator- (const Pos& rhs) const
    {
        return (x - rhs.x) * (x - rhs.x) + (y - rhs.y) * (y - rhs.y); 
    }
};
Pos point[V];
int map[V][V];

double Prim(int n)
{
    int* dist =map[0];          
    int c = n;
    double amount = 0.0;
    while (--c)
    {
        int add, min = INT_MAX;
        for (int i = 1; i < n; ++i)       
        {
            if (dist[i] != 0 && dist[i] < min)
            {
                add = i;
                min = dist[i];
            }
        }
        if (min == INT_MAX)           
            return -1;
        amount += sqrt((double)min);
        dist[add] = 0;                       
        for (int i = 1; i < n; ++i)        
        {
            if (map[add][i] < dist[i])
                dist[i] = map[add][i];
        }
    }
    return amount;
}

int main()
{
    int t;
    scanf ("%d", &t);
    while (t--)
    {
        int c;
        scanf ("%d", &c);
        for (int i = 0; i < c; ++i)
        {
            scanf ("%d %d", &point[i].x, &point[i].y);
            map[i][i] = 0;
            for (int j = 0; j < i; ++j)
            {
                int d = point[i] -point[j];
                if (d < 10 * 10 || d > 1000 * 1000)
                    d = INT_MAX;
                map[i][j] = map[j][i] = d;
            }
        }

        double amount = Prim(c);
        if (amount == -1)
            printf ("oh!\n");
        else
            printf ("%.1lf\n", amount * 100);
    }
    return 0;
}

　　

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#define MAXN 101 
#define MAXINT 99999999
using namespace std;
int n,m,num;
double ans;
int f[MAXN];
struct edge{
    int u,v,w;
    edge(int x=0,int  y=0,int z=0):u(x),v(y),w(z){};
}e[MAXN*MAXN];
struct node{
    int x,y;
}node1[MAXN];
int find(int x)
{
    if(x==f[x])
        return x;
    f[x]=find(f[x]);
    return f[x];
}
void Union(int x,int y,int z)
{
    int a=find(x);
    int b=find(y);    
    if(a==b) return ;
    f[b]=a;
    ans+=(double)sqrt((double)z);
}
int distance(int i,int j)
{
     return (node1[i].x-node1[j].x)*(node1[i].x-node1[j].x)+(node1[i].y-node1[j].y)*(node1[i].y-node1[j].y);
}
bool cmp(edge a,edge b)
{
    return a.w<b.w;
}
int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            f[i]=i;
            scanf("%d %d",&node1[i].x,&node1[i].y);
        }
        num=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<i;j++)
            {
                int tmp=abs(distance(i,j));
                if(tmp>1000000||tmp<100)
                    continue;
                e[num++]=edge(i,j,tmp);
            }
        sort(e,e+num,cmp);
        ans=0;
        for(int i=0;i<=num;i++)
            Union(e[i].u,e[i].v,e[i].w);
        int cou=0;
        for(int i=1;i<=n;i++)
            if(find(i)==i)
                cou++;
        if(cou>1) printf("oh!\n");
        else printf("%.1f\n",ans*100);
    }
    return 0;
}