Kruscal7组RuntimeError求助

求各位神犇帮我看看orz
type node=record
x,y,v:longint;
end;
var m,n,l:longint;
g:array[1..1000] of node;
father:array[1..1000] of longint;
max,cnt:longint;

procedure init;
var i:longint;
begin
read(n,m,l);
for i:=1 to m do
father[i]:=i;
for i:=1 to m do
read(g[i].x,g[i].y,g[i].v);
end;

procedure sort(l,r: longint);
var
i,j,x: longint;
y:node;
begin
i:=l;
j:=r;
x:=g[random(r-l+1)+l].v;
repeat
while g[i].v<x do
inc(i);
while x<g[j].v do
dec(j);
if not(i>j) then
begin
y:=g[i];
g[i]:=g[j];
g[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;

function getfather(v:longint):longint;
begin
if father[v]=v then exit(v)
else father[v]:=getfather(father[v]);
exit(father[v]);
end;

function union(x,y:longint):boolean;
var fx,fy:longint;
begin
fx:=getfather(father[x]);
fy:=getfather(father[y]);
father[fx]:=fy;
end;

procedure kruscal;
var ans,i:longint;
begin
cnt:=0;ans:=0;
for i:=1 to m do
if getfather(g[i].x) <> getfather(g[i].y) then
begin
union(g[i].x,g[i].y);
max:=max+g[i].v;
inc(cnt);
if cnt=n-l then break;
end;

end;

begin
randomize;
max:=0;
init;
sort(1,m);
kruscal;
if cnt=n-l then write(max)
else write('No Answer');
end.

2 条评论

  • @ 2014-05-24 19:54:34

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int n,m,k;
    int u[20010],v[20010],w[20010],p[20010],r[20010];
    int cmp(const int i,const int j) {return w[i]<w[j];}
    int find(int x)
    {
    if(p[x]==x) return x;
    int k=find(p[x]);
    p[x]=k;
    return k;

    }
    int kruskal()
    {
    int ans=0;
    for(int i=0;i<n;i++) p[i]=i;
    for(int i=0;i<m;i++) r[i]=i;
    sort(r,r+m,cmp);
    int kl=0;
    int i=0;
    while(kl<n-k&&i<m)
    {
    int e=r[i];
    int x=find(u[e]);
    int y=find(v[e]);
    if(x!=y)
    {
    kl++;
    ans=ans+w[e];
    p[x]=y;

    }

    i++;

    }

    if(kl<n-k) return -1;
    return ans;
    }
    int main()
    {

    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++)
    {
    scanf("%d%d%d",&u[i],&v[i],&w[i]);
    }
    int ans=kruskal();
    if(ans>0) printf("%d",ans);
    else printf("No Answer");
    return 0;

    }

  • @ 2014-04-17 17:34:32

    先谢过各位神了~orzorz

  • 1

信息

ID
1234
难度
5
分类
树结构 | 生成树 点击显示
标签
递交数
3664
已通过
1131
通过率
31%
被复制
8
上传者