HDU - 1875 畅通工程再续（最小生成树，Kruskal）

HDU - 1875

给定的x，y点坐标，求出两点的位置，转化成邻接表，走一遍Kruskal算法即可。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 110;
struct note
{
    int u,v;double w;
}e[N*N];
int f[N],x[N],y[N];
bool cmp(note a,note b) {
    return a.w<b.w;} 
int find(int x) {
    return f[x]==x?x:find(f[x]);} 
int n,cnt;
void Kruskal()
{
    double ans=0;for(int i=1;i<=n;i++) f[i]=i;sort(e+1,e+1+cnt,cmp);for(int i=1;i<=cnt;i++){
    int x=find(e[i].u);int y=find(e[i].v);if(x!=y) {
    f[x]=y;ans+=e[i].w;}}//printf("%d %d\n",cnt,m);int m=0;for(int i=1;i<=n;i++) if(f[i]==i) m++;if(m==1) printf("%.1f\n",ans*100);else puts("oh!");
} 
int main()
{
    int t;scanf("%d",&t); while(t--){
    scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]); cnt=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){
    double temp=(double)sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));if(temp>=10&&temp<=1000){
    e[++cnt].u=i;e[cnt].v=j;e[cnt].w=temp;
// printf("%lf\n",temp);}}Kruskal();}return 0;
}