CodeVS 2455 繁忙的都市 最小生成树
最近写的题都好水啊。。
题目大意：求一个无向图联通分量中边的数量和最长边。。
算法：最小生成树（Kruskal）其实是裸题。。
既然题目要求把所有点连起来，那么有n个点，那么就必定有n-1条边，所以第一个问就是来搞笑的，直接输出n-1嘛。
那么第二问求最小生成树联通分量的最长边，那么最小生成树跑一遍，再维护最长边就好啦。。
我写的是Kruskal，因为Kruskal比prim好理解一点（Kruskal其实就是贪心思想，每次给最小生成树加边），在稀疏图上跑的比较快。
代码：
1 var
2 a,b,v,p:array[1..100001] of longint;
3 n,m,i,ans,x,y,max:longint;
4 tot:int64;
5 procedure sort(l,r:longint);//快排再贪心
6 var
7 i,j,x,y:longint;
8 begin
9 i:=l;
10 j:=r;
11 x:=v[(l+r) div 2];
12 repeat
13 while x>v[i] do inc(i);
14 while x<v[j] do dec(j);
15 if i<=j then begin
16 y:=v[i];v[i]:=v[j];v[j]:=y;
17 y:=a[i];a[i]:=a[j];a[j]:=y;
18 y:=b[i];b[i]:=b[j];b[j]:=y;
19 inc(i); dec(j);
20 end;
21 until i>j;
22 if l<j then sort(l,j);
23 if i<r then sort(i,r);
24 end;
25 function doit(x:longint):longint;//最小生成树
26 begin
27 if p[x]=x then begin
28 doit:=x;
29 ans:=x;
30 end
31 else begin
32 doit:=doit(p[x]);
33 p[x]:=ans;
34 end;
35 end;
36 begin
37 readln(n,m);
38 max:=-maxlongint;
39 for i:=1 to m do readln(a[i],b[i],v[i]);
40 sort(1,m);
41 for i:=1 to n do p[i]:=i;
42 for i:=1 to m do begin
43 x:=doit(a[i]);y:=doit(b[i]);
44 if x<>y then begin
45 p[x]:=y;
46 if v[i]>max then max:=v[i];//维护最大值
47 end;
48 end;
49 writeln(n-1,' ',max);
50 end.
其实就是想放个模板。。
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。