hdu1875kruskal简单应用。

标记是dificulty 2，水，开始kruskal时练手题,只需开始时数据处理下，不符合要求的边不要，要理解并查集和Kruskal，就简单了，判断下是否联通图，（只需在记加入有效边时候统计连通分支数即可），生成树必是n-1条边，有效加入次数为n-1次，少与之便不连通了，在杭电总能1A。。。在POJ从未1A。。。。

#include<iostream>

#include<vector>

#include<algorithm>

#include<cstdio>

#include<cmath>

using namespace std;

const int inf=0x3f3f3f3f;

int fa[102];

int father(int x){return (x==fa[x]?x:father(fa[x]));}

struct edge

{

    int x,y;

    double w;

};

struct point

{

    int x,y;

};

bool my(const edge &a,const edge &b)

{

    return a.w<b.w;

}

int main()

{

    int tcase;scanf("%d",&tcase);

    int n;

    while(tcase--)

    {

       scanf("%d",&n);

       int x,y;

       vector<point>v(n); // 点集

       int m=n*(n-1)/2;

        vector<edge>vv(m);//  边集

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

         {

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

            fa[i]=i;

         }

         int num=0;

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

        {

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

             {

                 double tx=(v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y);

                 if(tx<100||tx>1000000)continue;

                 vv[num].w=sqrt(tx); vv[num].x=i;vv[num].y=j;

                 num++;

             }

        }

        sort(vv.begin(),vv.end(),my);

        double ans=0;int count=0;

        for(int i=0;i<m&&count<n-1;i++)

        {

            int xx=father(vv[i].x);int yy=father(vv[i].y);

            if(xx!=yy)   //不在同一个连通分量中。

            {

               ans+=vv[i].w*100;

               fa[xx]=yy;

               count++;      //有效加入该边。

            }

        }

        if(count<n-1)printf("oh!\n");

        else printf("%.1f\n",ans);

    }

}