源码:

Kruskal , K氏算法

相比与Prim,K似乎容易呢……(不妨去试一下P+Heap)。我是来解释一下呢,还是解释一下呢……

AC记录:#10

AC
0ms/5136KB

裸-克鲁斯卡尔-最小生成树

步骤:

1
2
3
4
1.将边排序
2.判断是否能插入此边,插入后做:
    1.inc(ans,路径长度)
    2.合并连通分支

意思是:你将边排了序,那么再判断是否能插入,当插入的边的个数为n-1的时候,就是最小生成树[贪心]。

如此的解释[对于插入]

背景:假如A是社会上的某个混混,他有很多老大。

达到什么条件插入?

A想跟B发生关系,但是他们的兄弟组合有规定,发生什么事情都要告诉老大先…A带着B去访问老大Y。Y叫A去见Z。但是他们没有带见面礼(100万什么的就免了),Z很不削。

1
2
3
Z刻薄的说:
1.你们两个不能是同一个血型的...
2.看见B,我很眼熟,我怀疑是我某个亲戚的亲戚的亲戚的女儿,如果是,那千万不能跟你这种小混混发生关系。(查找根是否相同来判断是否是一个联通分支,如果是,那么说明这个点已经合并过了,再合并会增加路径,不是最少的了)

1.A大笑:当然不是一个血型的(Z怀疑他在吹牛)。(i<>j,i点不能是j点)

2.A苦笑:那我怎么知道呢?

对于[刻薄的问题之2]的破解

A经历[刀山火海],找到了B的大爷爷,他问:“那个面容猥琐的Z是你家的吗?”大爷爷果断的说:“保定不是”。终于，B和A发生了关系…

但是有一个问题,大爷爷的辈份比Z高,也算加入了兄弟组合,他想当老大[另一个规矩]。Z说:“没关系,兄弟们都听我的,你当了只是摆一个架子而已”。

[讲正事]这里很像一个并查集,A要找老大,B要找大爷爷,他们不是一个连通分支的,所以可以合并[没有合并过]。而这2点合并了,应该合成一个连通分支,可是A有老大也有小弟,B有妹妹也有大爷爷,所以直接让根合并不就可以了。让Z做老大,或者大爷爷做老大,他们就是一个连通分支了。

关于路径压缩

A每次和别人发生关系都要找Y才能找Z。A很不喜欢Y这个老大,于是他就拿着100kuai去见了Z,“我住在你家旁边好不好?”

每一次找到根都可以直接把父节点指向根,这查找时就能很快。从[A]-[Y]-[Z]变为[A]-[Z],当然有些时候可以节省很多时间。

代码详解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
var
        fa:array[1..30000] of longint;//老大...
        a,b,c:array[1..30000] of longint;//b(起点)和c(终点)的长度为a
        i,j,n,m,k,l,ans:longint;//ans是答案

procedure sort(l,r:longint); var i,j,s,t:longint; begin i:=l; j:=r; s:=a[(l+r) div 2]; repeat while a[i]<s do i:=i+1; while a[j]>s do j:=j-1; if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; t:=b[i]; b[i]:=b[j]; b[j]:=t; t:=c[i]; c[i]:=c[j]; c[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;
//pascal手打排序,不必在意。注意,路径用来排序时起点和终点也要换

procedure start;//输入和排序,本人使用一维数组
var
        t,p:longint;
begin
        p:=0;
        read(n);
        for i:=1 to n do
                fa[i]:=i;
        for i:=1 to n do
                for j:=1 to n do
                begin
                        inc(p);
                        b[p]:=i;
                        c[p]:=j;
                        read(a[p]);
                        if i=j then
                                a[p]:=maxlongint;
                end;

        sort(1,n*n);
end;

function get(x:longint):longint;//找根...
begin
        if fa[x]=x then
                exit(x)
        else
        begin
                get:=get(fa[x]);//递归father
                fa[x]:=get;//路径压缩
        end;
end;

procedure min_way(x:longint);
var
        i,j:longint;
begin
        i:=b[x];//b点和c点要连边
        j:=c[x];
        if (i<>j) then//不是同一个点
        begin
                fa[i]:=get(i);//找老大
                fa[j]:=get(j);//找老大
                if (fa[i]<>fa[j]) then//不是同一个组合(不是同一个连通分支)
                begin
                        inc(ans,a[x]);//加上本路径
                        fa[get(j)]:=fa[i];//合并
                end;
        end;
        if x=n*n then//合并完成
                exit;
        min_way(x+1);//下一个需要合并的边
end;

begin
        start;
        min_way(1);
        writeln(ans);
end.