- 口袋的天空
- 2014-04-17 17:32:08 @
求各位神犇帮我看看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 条评论
-
兴华神将 LV 8 @ 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