HDU - 1875 畅通工程再续（并查集，最小生成树）
中文题目，一开始没有看清楚题目，WA了几发。
一开始我以为是一旦有两个岛之间的距离不在 10-1000范围之内就不符合条件，输出oh！错了几次以后再看题目，原来是在符合条件的岛屿之间修路，如果不能使得全部岛屿连通的时候才输出oh！
读题目很重要，读题目很重要，读题目很重要。
还好这个是中文题目，比较好找到，如果是英文题目，就要花更大功夫去读题目了。
解题思路：首先这个题目主要是考察最小生成树，这里我用的是Kruskal算法。因此需要用到并查集的知识。输入的时候处理边的关系，每读入一个点的坐标，和它之前的点的坐标求距离，如果距离在10-1000之间，那么就把这条边加入待选边中，在跑一遍最小生成树算法，如果最后找到的，也就是连通的点少于岛屿的数目-1，那么就连通不了所有岛屿，所有输出oh！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;
struct Edge
{
int from,to;
double cost;
}edge[10005];
struct Point
{
int x,y;
}point[105];
int fa[105],flag;
int t,num,k,cnt;
double sum;
int cmp(struct Edge a,struct Edge b){return a.cost<b.cost;}
int getfa(int x)
{
if(x==fa[x])
return x;
else
return fa[x]=getfa(fa[x]);
}
int merge(int u,int v)//把两个点归并到同一个集合
{
int t1,t2;
t1=getfa(u);
t2=getfa(v);
if(t1!=t2)
{
fa[t1]=t2;
return 1;
}
return 0;
}
void tree()//生成树算法
{
int i,j;
for(i=1;i<k;i++)
{
if(merge(edge[i].from,edge[i].to))//可以归并就归并到同一个集合
{
cnt++;
sum+=edge[i].cost;
}
if(cnt==num-1)//最后找到的点少于岛屿的数目-1
break;
}
if(cnt<num-1)
flag=0;
}
int main()
{
int i,j;
scanf("%d",&t);
while(t--)
{
sum=0; flag=1;//以下是初始化操作
k=1; cnt=0;
scanf("%d",&num);
for(i=1;i<=num;i++)
fa[i]=i;
for(i=1;i<=num;i++)
{
scanf("%d%d",&point[i].x,&point[i].y);
for(j=1;j<i;j++)//与前面读入的点求距离
{
int xx,yy;
double gap;
xx=abs(point[i].x-point[j].x);
yy=abs(point[i].y-point[j].y);
gap=sqrt(xx*xx+yy*yy);
if(gap<10||gap>1000)//不符合条件的边
continue;
else
{
edge[k].from=i;
edge[k].to=j;
edge[k].cost=gap*100;
k++;
}
}
}
sort(edge+1,edge+k,cmp);//对所有的边进行排序，从小到大
tree();
if(flag)
printf("%.1lf\n",sum);
else
printf("oh!\n");
}
}
/*测试数据
5
4
10 10
40 10
10 30
40 50
3
10 10
13 10
13 14
3
1 1
2 2
1000 1000
*/
