最小生成树 prim + kruskal

• prim 适用于稠密图
• kruskal 适用于稀疏图

AcWing 858. Prim算法求最小生成树

• prim 法的思路和 Dijkstra 基本一样，不同的是 d[N] 中是当前点到已访问点的集合即距离，只包含边权
• 即 g[u][v] < d[v] & w[v] < d[j]
• 区别于 g[u][v] + d[u] < d[v] & w[v] + d[u] < d[j]
• 此题是稀疏图，适用邻接矩阵，即边数明显大于顶点数

邻接矩阵

const int N = 510, INF = 0x3f3f3f3f;int g[N][N], n, m, d[N];bool visited[N];
int prim(int s)
{
    fill(d, d + N, INF);
    d[s] = 0;
    int sum = 0;
    for(int i = 1; i <= n; ++i)
    {
        int u = -1;
        for(int j = 1; j <= n; ++j)     // 错误！！ u 写成 n
            if(visited[j] == false && (u == -1 || d[j] < d[u]))
                u = j;
                
        if(d[u] == INF)
            return INF;
        visited[u] = true;
        sum += d[u];
        
        for(int v = 1; v <= n; ++v)
            if(visited[v] == false && g[u][v] != INF && g[u][v] < d[v])
                d[v] = g[u][v];
    }
    return sum;
}

int main()
{
    fill(g[0], g[0] + N * N, INF);
    cin >> n >> m;
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int ret = prim(1);
    if(ret > INF / 2)
        cout << "impossible";
    else
        cout << ret;
}
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

邻接表

const int N = 510, M = 1e6+10, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], n, m, idx = 0;
int d[N];
bool visited[N];
void add(int a, int b, int c){
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;}

int prim(int s)
{
    fill(d, d + N, INF);
    d[s] = 0;
    int sum = 0;
    for(int i = 1; i <= n; ++i)
    {
        // int u = -1, MIN = INF;
        // for(int j = 1; j <= n; ++j)
        // {
        //     if(visited[j] == false && d[j] < MIN)
        //     {
        //         MIN = d[j];
        //         u = j;
        //     }
        // }
        // if(u == -1)          // 存在不连通的情况，直接返回
        //     return INF;
        
        int u = -1;
        for(int j = 1; j <= n; ++j)
            if(visited[j] == false && (u == -1 || d[j] < d[u]))
                u = j;
        
        if(d[u] == INF)         // 存在不连通的情况，直接返回
            return INF;
        visited[u] = true;
        sum += d[u];            // 累加边权
        for(int v = h[u]; v != -1; v = ne[v])
        {
            int j = e[v];   
            if(visited[j] == false && w[v] < d[j])
                d[j] = w[v];    // 这里判断的只是边权 w[v] ，区分于dijkstra的 d[u] + w[v]
        }
    }
    return sum;
}

int main()
{
    fill(h, h + N, -1);
    cin >> n >> m;
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        // if(a == b)   // 对于指向自己的边(自环)，不用预处理
        //     continue;// 因为会有 visited[N] 自动将自环排除
        add(a, b, c);   // 无向图
        add(b, a, c);
    }
    int ret = prim(1);
   if(ret > INF / 2)
        cout << "impossible";
    else
        cout << ret;
    
    return 0;
}
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

AcWing 859. Kruskal算法求最小生成树

• kruskal 是边权贪心的策略，利用并查集实现(用来判断是否在同一连通块)
• 所有边按照边权升序排序，按顺序循环
• 不在同一连通块的顶点进入最小生成树的统计
• 若在同一连通块，则不统计，避免成环

const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f;
int n, m, p[N];
struct Edge{
    int u, v, w;
    bool operator< (const Edge &e) const{
        return w < e.w; } // 使用sort实现 < 即可
}E[M];
int findP(int c){
    if(p[c] != c)
        p[c] = findP(p[c]);
    return p[c];	}

int kruskal()
{
    sort(E, E + m);				// 所有边按照边权升序排序
    for(int i = 1; i <= n; ++i)	// 预处理并查集
        p[i] = i;
    int sum = 0, cnt = 0;
    for(int i = 0; i < m; ++i)
    {
        int pu = findP(E[i].u), pv = findP(E[i].v);
        if(pu != pv)			// 不在同一连通块，则统计树的总权和总边数
        {
            p[pu] = pv;
            sum += E[i].w;
            cnt++;
        }
    }
    if(cnt != n - 1)    		// 判断最后的边数
        return INF;
    return sum;
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; ++i)
        cin >> E[i].u >> E[i].v >> E[i].w;
    int ret = kruskal();
    if(ret == INF)
        cout << "impossible";
    else
        cout << ret;
}

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