以下部分摘自《算法竞赛进阶指南》

最小生成树

常用算法

kruskal

KruskalKruskal总是维护无向图的最小生成森林。
KruskalKruskal从剩余的边中选出一条权值最小的边，并且这条边的两端分属于不同的集合（即生成森林中不同的两棵树）；把这条边加入生成森林中。使用并查集来维护结点的连通情况。

实现步骤

1、建立并查集，最初时每个点各自为一个集合。
2、把所有边按照权值从小到大排序。
3、扫描每条边
如果这条边连接两个不同的树，合并这两个点，并将边权加入答案。
否则忽略这一条边。

时间复杂度

O(mlogm)O(mlogm)

常用情况

基本都用。有的题使用KruskalKruskal做起来很方便，而用primprim很困难。

代码实现

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
const int M = 5e4 + 8,N = 2e3 + 8;
int fa[N],n,m,ans;
struct rec{
    int x,y,z;
}edge[M];//结构体储存边
bool operator < ( rec a, rec b) {
    return a.z < b.z;
}//重载小于号

int find(int x) {
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}//并查集

int main() {
    cin >> n >> m;
    for (int i =1; i <= n; i ++ ) fa[i] = i;
    for (int i =1;  i<= m;i ++) {
		int u,v,w;
		cin >> u >> v >> w;
		edge[i] = {u,v,w};
 	}
    sort(edge+1, edge+1+m);//按找边权从小到大排序
    for (int i =1; i <= m; i ++ ) {
        int x = find(edge[i].x ) , y = find(edge[i].y);
        if (x == y) continue;//如果两个点属于同一集合就跳过
        fa[x] = y;//合并两个集合
        ans += edge[i].z;//将符合条件的边权累加到答案中
    }
    cout << ans << endl;
}

朴素prim

设已经确定属于最小生成树的结点集为TT，其余结点集为SS。primprim算法找到minx∈S,y inT{z}min_{x \in S,y\ inT}\{z\}，即两个结点分别属于S,TS,T的权值最小的边。然后把结点从SS中删除并加入TT。
类比最短路中的DijkstraDijkstra算法，使用一个数组标记结点是否属于TT。每次从未被标记的结点中选出dd值最小的，把它标记，同时扫描所有出边，更新另一个端点的dd值。

时间复杂度

O(n2)O(n^2)

常用情况

邻接矩阵/稠密图

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int g[N][N],d[N];//邻接矩阵，距离
int n,m;//点数量，边数量
bool v[N];//标记数组
void prime(){
    memset(d,0x3f,sizeof d);//将距离初始化为正无穷
    d[1] = 0;//将1号点加入最小生成树
    for (int i =1; i  <= n; i++){
        int t = -1;
        for (int j =1; j <= n; j++)if (!v[j] && ( t == -1 || d[j] < d[t])) t = j;
        //找到点不在最小生成树中，并且连接最小生成树与其余点集的最小边
        v[t] = 1;//加入最小生成树
        for (int j= 1; j <= n;j ++)if (!v[j]) d[j] = min(d[j],g[t][j]);
        //更新其他点（不在最小生成树中的）到新加入最小生成树的点的最小距离
    }
}

堆优化prim

可以使用二叉堆将时间复杂度优化到O(mlogn)O(mlogn)。但是堆优化primprim不如KruskalKruskal方便，所以基本不用。

例题

1、模板题

2、连接格点

题意

给出一个n∗mn*m的方格以及一些已经连通的初始边，相邻两点可以相连。其中横向边权值为2，纵向边权值为1，求最小生成树。

思路

初始边为必选边，然后将其他所有边都建好，跑一边最小生成树即可。

代码
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
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e7 + 8000;
int n,m;
int fa[N];

int find(int x) { 
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}

int ask (int x,int y) {
    return (x - 1) * m + y;
}

struct rec{
    int x,y,z;
}edge[N];

bool operator <(rec a, rec b) {
    return a.z < b.z;
}

int main () {int res = 0;
    cin >> n >> m;
    for (int i = 1; i <= n * m; i ++ ) fa[i] = i;
    int x1,y1,x2,y2;
    while (cin >> x1 >> y1 >> x2 >> y2) {//读入初始边并合并所连的点
        int x = ask(x1,y1), y = ask(x2,y2);
        x = find(x), y =find(y);
        fa[x] = y;
    }
    int tot = 0;

    for (int i = 1; i <= n; i ++ ) //建横向边
        for (int j =1; j < m; j ++) {
            int x, y;
            x = ask(i,j), y =ask(i,j+1);
            edge[++tot].x = x,edge[tot].y = y;
            edge[tot].z = 2;
        }
    for (int i = 1; i <= m; i ++ ) //建纵向边
        for (int j = 1; j < n; j ++ ) {
            int x ,y;
            x = ask(j,i), y = ask(j + 1,i);
            edge[++tot].x = x,edge[tot].y = y;
            edge[tot].z = 1;
        }
    sort(edge+1,edge+1+tot);
    for (int i =1; i <= tot; i ++ ) {
        int x = find(edge[i].x), y = find(edge[i].y);
        if (x == y) continue;
        fa[x] = y;
        res += edge[i].z;
    }
    cout << res << endl;
}

/*
m*(x-1) + y;
1 2 3 4 
5 6 7 8
*/

3、新的开始

题意
思路

建立一个虚拟源点，将有点权的点与虚拟源点相连。这样原图变成一个有n+1n+1个结点的无向图，带有点权的点转化为有一条从源点到该点的边，且权值为原来点权权值。

代码
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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 555;

int a[N][N],d[N],n,m,ans;

bool v[N];
void prim() {
    memset(d,0x3f,sizeof d);
    memset(v,0,sizeof v);
    d[0] = 0;
    for (int i = 0; i < n; i ++ ) {
        int x = -1;//如果虚拟源点设为0，这里的x不能设置为0
        for (int j = 0; j <= n;  j++ )
            if (!v[j] && ( x == -1 || d[j] < d[x])) x = j;
        v[x] = 1;
        for (int j = 0; j <= n; j ++ )
            if(!v[j]) d[j] = min(d[j],a[x][j]);
    }
}

int main () {
    cin >> n;
    memset(a,0x3f,sizeof a);
    for (int i = 1; i <= n; i ++ ) {
        int x;
        cin >> x;
        a[0][i] = a[i][0] = x;
    }
    for (int i = 0; i <= n; i ++ ) a[i][i] = 0;
    for (int i = 1; i <= n; i++)
        for (int j =1; j <= n; j ++ ) cin>>a[i][j];
    prim();
    for (int i = 0; i <= n; i ++ ) 
    if (d[i] != 0x3f3f3f3f) ans += d[i];
    cout << ans << endl;
}

4、 POJ1789

题意

给定NN个字符串，某个字符串转为另一个字符串的花费为他们每一位不相同的字符数。 求最小花费QQ。

思路

记录各字符串不相同的字符数量，跑一遍最小生成树。

代码
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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
#define endl '\n'
#define fi first
#define se second
#define ee edge
typedef pair<int,int> PII;
typedef double ff;
typedef long long ll;
const int N = 2e3 + 9,M = 6e6 + 10,INF = 0x3f3f3f3f;

int fa[N*N/2];
int n,m,tot;
int find(int x) {
    if (x != fa[x]) fa[x] = find(fa[x]); 
    return fa[x];
}
struct rec { 
    int x,y,d;
}edge[N*N/2];
bool operator< ( rec a, rec b) {
    return a.d < b.d;
}

ff dist(ff x1, ff y1 , ff z1,ff x2 , ff y2,ff z2 ) {
    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + (z1-z2)*(z1-z2));
}

char q[N][2005];

int main () {
    while(cin >> n,n) {
        memset(edge,0,sizeof edge);
        tot = 0;
        memset(q,'\0',sizeof q);
        for (int i = 0; i < n; i ++ ) {
            scanf("%s",q[i]);
        }
        for (int i =  0;  i< n ;i ++ ) {
            for (int j = i + 1; j < n; j ++ ) {
                int cnt = 0;
                for (int k = 0; k < 7; k ++ )
                if (q[i][k] != q[j][k]) cnt++;
                edge[++tot].x = i + 1,edge[tot].y = j + 1, edge[tot].d = cnt;
            }
        }
        for  (int i = 1;i <= tot; i ++ )fa[i] = i;
        sort(edge+1,edge+1+tot);
        int ans = 0;
        for (int i = 1; i <= tot; i ++) {
            int x = find(edge[i].x), y = find(edge[i].y);
            if (x == y ) continue;
            fa[x] = y;
            ans += edge[i].d;
        }
        printf("The highest possible quality is 1/%d.\n",ans);
    }
}

习题

1、 POJ2349

最小生成树的扩展应用

2、 POJ1751

记录方案

3、POJ3026

搜索+最小生成树

4、走廊泼水节

维护额外信息

5、KD-tree

6、Black and white