本文共 1441 字，大约阅读时间需要 4 分钟。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int n,m,aa,bb,f[1000005],xxx[1000005],yyy[1000005];struct date{   	int x,y;	double sqr;}a[1000005];int find(int x){   	if(f[x]!=x)	f[x]=find(f[x]);	return f[x];}bool cmp(date a,date b){   	return a.sqr
       
        >n>>m;	for(i=1;i<=n;i++)	cin>>xxx[i]>>yyy[i];	for(i=1;i<=n;i++)	f[i]=i;	for(i=1;i<=n;i++){   		for(j=i+1;j<=n;j++){   			a[l].x=i;			a[l].y=j;			a[l++].sqr=(double)sqrt((double)(xxx[i]-xxx[j])*(xxx[i]-xxx[j])+(double)(yyy[i]-yyy[j])*(yyy[i]-yyy[j]));		}	}	for(i=1;i<=m;i++){   		cin>>aa>>bb;		a[l].x=aa;		a[l].y=bb;		a[l++].sqr=0.0;	}	//kruskal	sort(a+1,a+1+l,cmp);	double ans=0.0;	for(i=1;i<=l;i++){   		aa=a[i].x;		bb=a[i].y;		if(find(aa)==find(bb))		continue;		f[find(aa)]=find(bb);		ans+=a[i].sqr;	}	printf("%.2lf",ans);		return 0;}
       
      
     
    
   

这题与最小生成树大致是一样的，使用kruskal算法模板，差别在于，此题没有给出节点权值，需要自己求出，并且使给出的节点权值为0，这样在求和时，就不会再多加。

优雅又不尴尬的分界线

刚开始在洛谷写的写对了，然后再poj上遇见，给提交了，昨夜搞了仨小时没过，还是老样子，有空再改吧

输入格式

• Line 1: Two space-separated integers: N and M

• Lines 2…N+1: Two space-separated integers: Xi and Yi

• Lines N+2…N+M+2: Two space-separated integers: i and j, indicating that there is already a road connecting the farm i and farm j.

输出格式

• Line 1: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to
  calculate distances as 64-bit floating point numbers.