首页 > 代码库 > 初学并查集-2：最优布线问题
初学并查集-2：最优布线问题
题目描述 Description
学校需要将n台计算机连接起来，不同的2台计算机之间的连接费用可能是不同的。为了节省费用，我们考虑采用间接数据传输结束，就是一台计算机可以间接地通过其他计算机实现和另外一台计算机连接。
为了使得任意两台计算机之间都是连通的（不管是直接还是间接的），需要在若干台计算机之间用网线直接连接，现在想使得总的连接费用最省，让你编程计算这个最小的费用。
输入描述 Input Description
输入第一行为两个整数n,m（2<=n<=100000，2<=m<=100000），表示计算机总数，和可以互相建立连接的连接个数。接下来m行，每行三个整数a,b,c 表示在机器a和机器b之间建立连接的话费是c。(题目保证一定存在可行的连通方案, 数据中可能存在权值不一样的重边，但是保证没有自环)
输出描述 Output Description
输出只有一行一个整数，表示最省的总连接费用。
样例输入 Sample Input
3 3
1 2 1
1 3 2
2 3 1
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
最终答案需要用long long类型来保存
type r=record x,y,v:longint; end;var n,m:longint; total:int64; used:array[1..100000]of boolean; cost:array[1..100000]of r; father:array[1..100000]of longint; i,j,k,l:longint; line:longint;procedure qsort(i,j:longint); var head,tail,k:longint; temp:r; begin head:=i; tail:=j; k:=cost[(head+tail) div 2].v; while head<tail do begin while cost[head].v<k do inc(head); while k<cost[tail].v do dec(tail); if head<=tail then begin temp:=cost[head]; cost[head]:=cost[tail]; cost[tail]:=temp; inc(head); dec(tail); end; end; if head<j then qsort(head,j); if i<tail then qsort(i,tail); end;function find(x:longint):longint; begin if father[x]=x then exit(x); father[x]:=find(father[x]); exit(father[x]); end;procedure union(x,y:longint); begin father[find(x)]:=find(father[y]); end;begin total:=0; readln(n,m); fillchar(used,sizeof(used),true); fillchar(cost,sizeof(cost),0); for i:=1 to n do father[i]:=i; for i:=1 to m do readln(cost[i].x,cost[i].y,cost[i].v); qsort(1,m); line:=0; i:=0; while i<=m do begin inc(i); if find(cost[i].x)<>find(cost[i].y) then begin inc(line); union(cost[i].x,cost[i].y); inc(total,cost[i].v); end; end; writeln(total);end.
初学并查集-2：最优布线问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。