poj3164 最小树形图板子题

/*

思路很简单，也不知道哪里错了TAT

*/

/*

N个点通过笛卡尔坐标表示

根节点是1，求最小树形图

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define MAXN 105

#define INF 0x3f3f3f3f

using namespace std;

struct Edge{

     int u,v;

     double cost;

     Edge(int uu=,int vv=,double cc=0.0):u(uu),v(vv),cost(cc){}

}edge[MAXN*MAXN];

struct node{

     int x,y;

}nodes[MAXN];

double dist(int u,int v){

     return sqrt((double)(nodes[u].x-nodes[v].x)*(nodes[u].x-nodes[v].x)+

                  (nodes[u].y-nodes[v].y)*(nodes[u].y-nodes[v].y));

}

int pre[MAXN],id[MAXN],vis[MAXN];

double in[MAXN];

double zhuliu(int root, int nv, int ne)

{

    double ans = ;

    int u, v, i, cnt;

    while(true){

        //0.初始化

        for(i = ; i <= nv; ++i) in[i] = INF;

        //1.找最小入边集

        for(i = ; i <= ne; ++i){

            u = edge[i].u; v = edge[i].v;

            if(edge[i].cost < in[v] && u != v){

                in[v] = edge[i].cost; pre[v] = u;

            }

        }

        for(i = ; i <= nv; ++i)

            if(in[i]==INF && i!=root)

                return -;

        //2.找非根无入边点(略)，因为必定有解

        //3.找环，加权，重新标号

        memset(id, -, sizeof(id));

        memset(vis, -, sizeof(vis));

        cnt = in[root] = ;

        for(i = ; i <= nv; ++i){

            ans += in[i]; v = i;

            while(vis[v] != i && v != root && id[v] == -){

                vis[v] = i; v = pre[v];

            }

            if(v != root && id[v] == -){

                for(u = pre[v]; u != v; u = pre[u])

                    id[u] = cnt;

                id[v] = cnt++;

            }

        }

        if(cnt == ) break; //无环，算法完成

        for(i = ; i <= nv; ++i)

            if(id[i] == -) id[i] = cnt++;

        //4.缩点，遍历每一条边，重新构图

        for(i = ; i <= ne; ++i){

            v = edge[i].v;

            edge[i].u = id[edge[i].u];

            edge[i].v = id[edge[i].v];

            if(edge[i].u != edge[i].v) edge[i].cost -= in[v];

        }

        //顶点数减少

        nv = cnt; root = id[root];

    }

    return ans;

}

int main(){

     int n,m,u,v;

     while(scanf("%d%d",&n,&m)==){

         for(int i=;i<=n;i++)

             scanf("%d%d",&nodes[i].x,&nodes[i].y);

         int totm=;

        for(int i=;i<=m;i++){

             scanf("%d%d",&u,&v);

             if(u!=v)

                 edge[++totm]=Edge(u,v,dist(u,v));

         }

         int root=;

         double res=zhuliu(root,n,totm);

         if(res==-)

             puts("poor snoopy");

         else

             printf("%.2lf\n",res);

     }

     return ;

}