题解 P2212 【[USACO14MAR]浇地Watering the Fields】

题解 P2212 【[USACO14MAR]浇地Watering the Fields】

这题怎么没有psacal题解啊QAQ,那我来水一发~~

这题就是最小生成树的板题啊...

把可以连的边放入一个序列，然后跑最小生成树

我用的是克鲁斯卡尔(不会打prim)

就是注意算距离是要判断是否大于工人期望的钱数

还有就是要注意-1(我就是这个地方卡了很长时间)

直接上代码吧

var
a,b,v,p,x,y:array[0..10000005] of longint;//数组其实不用这么大，还是为了省事
n,m,i,t,t1,k,mm,j,xx,yy:longint;
s:int64;//以防万一开longlong
procedure qsort(l,r:longint);
var
i,j,mid,t:longint;
begin
i:=l; j:=r; mid:=v[(l+r) div 2];
repeat
while v[i]<mid do inc(i);
while mid<v[j] do dec(j);
if i<=j then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
t:=b[i];
b[i]:=b[j];
b[j]:=t;
t:=v[i];
v[i]:=v[j];
v[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function find(u:longint):longint;
begin
if p[u]=u then exit(u);
p[u]:=find(p[u]);
exit(p[u]);
end;//并查集find操作
begin
readln(n,mm);
for i:=1 to n do
readln(x[i],y[i]);
for i:=1 to n do
for j:=1 to n do
begin
if i=j then continue;
s:=(x[i]-x[j])(x[i]-x[j])+(y[i]-y[j])(y[i]-y[j]);//算欧几里得距离
//writeln(s);
if s>=mm then
begin
inc(m);
a[m]:=i;
b[m]:=j;
v[m]:=s;
end;//判断是否符合要求，符合的就加入序列
end;
//writeln(m);
qsort(1,m);//克鲁斯卡尔的排序
for i:=1 to 1000000 do p[i]:=i;//并查集，为了省事直接开到1000000
s:=0;
t:=0;
for i:=1 to m do
begin
xx:=find(a[i]); yy:=find(b[i]);
if xx<>yy then
begin
p[xx]:=yy;
inc(t);
s:=s+v[i];
end;//并查集合并操作，t表示合并的次数
end;
//writeln(t);
if t=n-1 then writeln(s) else writeln(-1);//如果合并了t-1次，那么说明联通，否则就输-1
end.