HDU4463(最小生成树)

模版稍微改一下，Prime在搜到其中一个点时直接把另一条边加入即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define LEN 110
#define INF 0x7fffffff
using namespace std;

int n;
typedef struct {
    int x, y;
}POINT;

POINT store[LEN];
int ta, tb;
double map[LEN][LEN], dis[LEN];
int vis[LEN];

double prime(int vex)
{
    double sum = 0;
    memset(vis, 0, sizeof vis);
    memset(dis, 0, sizeof dis);
    vis[0]=1;
    for(int i=0; i<n; i++)
        dis[i] = map[vex][i];
    for(int i=0; i<n-1; i++)
    {
        int min;
        double minsize = INF;
        if(vis[ta]+vis[tb]==1){
            minsize = map[ta][tb];
            min = ((i==ta)?tb:ta);
            vis[min] = 1;
            sum += minsize;
            for(int j=0; j<n; j++)
                if(map[min][j]<dis[j])
                    dis[j] = map[min][j];
        }
        else{
            for(int j=0; j<n; j++){
                if(minsize>dis[j] && vis[j]==0){
                    min = j;
                    minsize = dis[j];
                }
            }
            vis[min] = 1;
            sum += minsize;
            for(int j=0; j<n; j++)
                if(map[min][j]<dis[j])
                    dis[j] = map[min][j];
        }
    }
    return sum;
}

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

void build()
{
    scanf("%d%d", &ta, &tb);
    ta--;tb--;
    for(int i=0; i<n; i++){
        scanf("%d%d", &store[i].x, &store[i].y);
    }
    for(int i=0; i<n; i++)
    for(int j=0; j<n; j++){
        map[i][j] = Dis(store[i], store[j]);
    }
}

int main()
{
//    freopen("in.txt", "r", stdin);

    while(scanf("%d", &n)!=EOF && n)
    {
        build();
        printf("%.2lf
", prime(0));
    }
    return 0;
}