注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【MST】【最优布线】  

2013-11-01 12:31:43|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
  以前是很傻叉的不用并查集的,然后现在才看出来原来那个做法哪里不对了...
===========================================================================
program kruskal;
var
n,m:longint;
a,b,c:array[1..100000]of int64;
ans:int64;
f,d:array[1..100000]of longint;

function find(x:longint):longint;
begin
  if f[x]=x then exit(x);
  f[x]:=find(f[x]);
  exit(f[x]);
end;

procedure union(a,b:longint);
var x,y:longint;
begin
  x:=find(a);y:=find(b);
  if x=y then exit;
  if d[x]<=d[y] then
   begin
     f[x]:=y;
     d[y]:=d[x]+d[y];
    end
   else
    begin
     f[y]:=x;
     d[x]:=d[x]+d[y];
    end;
end;

procedure swap(var a,b:int64);
var c:int64;
begin
  c:=a;a:=b;b:=c;
end;

procedure qsort(l,r:longint);
var i,j:longint;
    x,y:int64;
begin
  i:=l;j:=r;
  x:=c[(l+r)shr 1];
  repeat
    while c[i]<x do inc(i);
    while c[j]>x do dec(j);
    if i<=j then begin
      swap(c[i],c[j]);
      swap(a[i],a[j]);
      swap(b[i],b[j]);
      inc(i);dec(j);
     end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;

procedure main;//kruskal;
var i,j:longint;
begin
  qsort(1,m);
  for i:=1 to n do f[i]:=i;
  for i:=1 to n do d[i]:=1;
  j:=0;
  ans:=0;
  for i:=1 to m do
      if find(a[i])<>find(b[i]) then 
      begin
      inc(ans,c[i]);
      inc(j);
      union(a[i],b[i]);
      if j=n-1 then break;
      end;
  write(ans);
end;

procedure init;
var i:longint;
begin
  read(n);read(m);
  for i:=1 to m do
    begin
      read(a[i]);read(b[i]);read(c[i]);
    end;
end;
begin
  init;
  main;
end.

			
  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018