讨论 / 大牛帮忙看一下
lfwdj1992 2008-07-04 02:59:00
点我顶贴 收藏 删除
我用kruskai做的,几乎是书上的标程,可为什么样例对了,

其他的却一个都不对呢?

type

s=set of 1..200;

re=record

l,r:longint;

len:longint;

end;

var

vset:array[1..100] of s;

e:array[1..20000] of re;

n,i,j,p,q,t:longint;

x:qword;

tot:qword;

procedure sort(l,r:integer);

var

i,j:longint;

x:longint;

t:re;

begin

x:=e[(l+r)div 2].len; i:=l; j:=r;

repeat

while e[i].len<x do inc(i);

while e[j].len>x do dec(j);

if i<=j then begin t:=e[i]; e[i]:=e[j]; e[j]:=t; inc(i); dec(j); end;

until i>j;

if i<r then sort(i,r);

if j>l then sort(l,j);

end;

function find(v:longint):longint;

var

i:longint;

begin

i:=1;

while (i<=n)and(not(v in vset[i])) do inc(i);

if i<=n then find:=i else find:=0;

end;

begin

readln(n);

for i:=1 to n do

for j:=1 to n do

begin

read(x);

if x<>0 then begin

inc(t); e[t].l:=i; e[t].r:=j; e[t].len:=x; end;

end;

sort(1,t);

for i:=1 to n do vset[i]:=[i];

p:=n-1; q:=1; tot:=0;

while p>0 do

begin

i:=find(e[q].l); j:=find(e[q].r);

if i<>j then begin

vset[i]:=vset[i]+vset[j]; vset[j]:=[]; inc(tot,e[q].len); dec(p); end;

inc(q);

end;

write(tot);

end.

#1 LQY123@2008-06-28 03:40:00
回复 删除
同感

就是不知道为什么……

不过我又换了一种做法 就ac了

难不成是灵异事件?

#2 lfwdj1992@2008-06-28 04:53:00
回复 删除
刚刚反应过来,kruskal和prim都只能求无向图的最小生成树,可这题是有向图的(网上找不到算法),ac的大牛能不能给讲讲怎么做?

万分感谢!

#3 lfwdj1992@2008-07-04 02:59:00
回复 删除
无语了,看错题了......
查看更多回复
提交回复