UC知道Vijos1234 Kruscal
来源：百度知道 编辑：UC知道 时间：2024/06/30 09:25:15
晕了 编了个Kruscal不知道错哪里。-，-
源程不带空格，嫌麻烦就不要看
注意是找错，算法什么的我已经了解了
复制粘贴程序或是解题报告小心我举报= =+
n表示点的个数，m表示边的个数，l表示棉花糖串数
f[]表示并查集的根节点
min是代价最小和
s[]是边的权值
x,y
qsort和getfather都是函数，分别代表快排和并查集
（感觉是并查集的那块搞错了）
qsort(1,m);
for i:=1 to n do
f[i]:=i;
j:=1;
if n-l>m then begin writeln('No Answer');exit;end;
for i:=1 to n-l do
begin
while (getfather(x[j])=getfather(y[j])) and (j<=m) do inc(j);
if j>m then begin writeln('No Answer');exit;end;
if getfather(x[j])<>getfather(y[j]) then begin
f[y[j]]:=f[x[j]];
min:=min+s[j];
end;
end;
writeln(min);
end.
源程不带空格，嫌麻烦就不要看
注意是找错，算法什么的我已经了解了
复制粘贴程序或是解题报告小心我举报= =+
n表示点的个数，m表示边的个数，l表示棉花糖串数
f[]表示并查集的根节点
min是代价最小和
s[]是边的权值
x,y
qsort和getfather都是函数，分别代表快排和并查集
（感觉是并查集的那块搞错了）
qsort(1,m);
for i:=1 to n do
f[i]:=i;
j:=1;
if n-l>m then begin writeln('No Answer');exit;end;
for i:=1 to n-l do
begin
while (getfather(x[j])=getfather(y[j])) and (j<=m) do inc(j);
if j>m then begin writeln('No Answer');exit;end;
if getfather(x[j])<>getfather(y[j]) then begin
f[y[j]]:=f[x[j]];
min:=min+s[j];
end;
end;
writeln(min);
end.
附程序，已在VJ上AC，请自行对照，希望对您有帮助。
const maxn=1001;
maxm=10001;
type arr=array[1..3] of integer;
var
v:array[1..maxm] of arr;
fa:array[1..maxn] of integer;
n,m,k,i,f1,f2,line:integer;
ans:longint;
function father(x:integer):integer;
begin
if fa[x]=0 then exit(x)
else exit(father(fa[x]));
end;
procedure qsort(l,r:integer);
var
i,j,x:integer;
t:arr;
begin
i:=l; j:=r; x:=v[(i+j) shr 1,3];
repeat
while v[i,3]<x do inc(i);
while x<v[j,3] do dec(j);
if i<=j then
begin
t:=v[i];
v[i]:=v[j];
v[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
begin
readln(n,m,k);
if m<n-k then
begin
writeln('No Answer');
halt;
end;