题意：n个点，m条已有的边，建一些新边，代价为两点间的欧几里得距离，使得n个点联通，求最少的代价
...高仿kruscal..
先把已经连上的连上，然后再把没有连上的边从小到大排序，按kruscal的套路去跑就行了（详见代码）
注意：再求欧几里得距离的时候，由于x和y的范围为10^6，会爆int，要强转long long（int64）
type rec=record a,b:longint; len:double; end; var n,m,tot,tt,tx,ty:longint; xx,yy :longint; i,j :longint; l :array[0..1000010] of rec; x,y,father :array[0..1010] of longint; ans :double; function get_father(x:longint):longint; begin if x=father[x] then exit(x); father[x]:=get_father(father[x]); exit(father[x]); end; procedure sort(ll,rr:longint); var i,j:longint; x:double; y:rec; begin i:=ll; j:=rr; x:=l[(ll+rr)>>1].len; while (i<=j) do begin while l[i].len<x do inc(i); while l[j].len>x do dec(j); if (i<=j) then begin y:=l[i]; l[i]:=l[j]; l[j]:=y; inc(i); dec(j); end; end; if i<rr then sort(i,rr); if j>ll then sort(ll,j); end; begin read(n,m); for i:=1 to n do father[i]:=i; for i:=1 to n do read(x[i],y[i]); for i:=1 to m do begin read(xx,yy); tx:=get_father(xx); ty:=get_father(yy); if tx<>ty then begin father[tx]:=ty; inc(tt); end; end; // for i:=1 to n do for j:=i+1 to n do if get_father(i)<>get_father(j) then begin inc(tot); l[tot].a:=i; l[tot].b:=j; l[tot].len:=sqrt(int64(x[i]-x[j])*int64(x[i]-x[j])+int64(y[i]-y[j])*int64(y[i]-y[j])); end; sort(1,tot); ans:=0; for i:=1 to tot do if tt=n-1 then break else begin tx:=get_father(l[i].a); ty:=get_father(l[i].b); if tx<>ty then begin father[tx]:=ty; inc(tt); ans:=ans+l[i].len; end; end; writeln(ans:0:2); end. ——by Eirlys
