ACM UVA-10034

這題是典型的Minimum Spanning Tree,我用Prims Algorithm。

//ignore header files
#define dis(p1,p2) sqrt(((p1.x-p2.x)*(p1.x-p2.x))+((p1.y-p2.y)*(p1.y-p2.y)))
struct point{
    double x,y;
    int num;
    point(double a,double b,int c){
        x = a;
        y = b;
        num = c;
    }
};
struct Edge{
    int n;
    double dis;
    Edge(int a,double b){
        n = a;
        dis = b;
    }

};
int main(int argc, char const* argv[])
{
    int m;
    while(scanf("%d",&m) != EOF){
        for(int k = 0;k<m;k++){
            int n;
            double sum = 0;
            bool visit[105];
            scanf("%d",&n);
            vector<Edge> G[105];
            double d[105];
            for(int i = 0;i<n;i++){
                d[i] = 1e9;
                visit[i] = 0;
            }
            vector<point> v;
            for(int i = 0;i < n;i++){
                double x,y;
                scanf("%lf %lf",&x,&y);
                v.push_back(point(x,y,i));
            }
            for(size_t i = 0;i<v.size()-1;i++)
                for(size_t j = i+1;j<v.size();j++){
                    double w = dis(v[i],v[j]);
                    G[v[i].num].push_back(Edge(v[j].num,w));
                    G[v[j].num].push_back(Edge(v[i].num,w));
                }

            d[0] = 0;
            for(int i = 0;i<n;i++){
                int a = -1;
                int min = 1e9;
                for(int j = 0;j<n;j++){
                    //找離MST最近的點
                    if(!visit[j] && d[j]<min){
                        a = j;
                        min = d[j];
                    }
                }
                if(a == -1)
                    break;
                visit[a] = true;
                //抓到新的點,把MST到該點的距離加到sum中
                sum = sum+d[a];
                //檢查該點的鄰居
                for(size_t j = 0;j<G[a].size();j++){
                    int b = G[a][j].n;
                    if(!visit[b] && G[a][j].dis<d[b]){
                        //更新此點到MST的距離
                        d[b] = G[a][j].dis;
                    }
                }
            }
            if(k == 0)
                printf("%.2lf\n",sum);
            else
                printf("\n%.2lf\n",sum);

        }
    }
    return 0;
}