最小生成树

最小生成树

mi0e

February 7, 2023

702 views

No comments

750 words

C/C++

# 最短生成树

## Prim

```cpp
#include<iostream>
#include<cstring>
using namespace std;

const int N = 505, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

intprim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;   // 第一个点一定在最小生成树中

int res = 0;  // 用来存放权值之和
    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

if(dist[t] == INF) return INF;   // 尽早跳出循环防止TLE，如果不加则需要在输出的地方更改
        res += dist[t];
        st[t] = true;

for(int j = 1; j <= n; j ++)
            dist[j] = min(dist[j], g[t][j]); // 注意和dijkstra的区别
                                             // prim的dist是到已经生成的树的最短距离
    }
    return res;
}

intmain()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);

while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

int t = prim();

if(t == INF) cout << "impossible" << endl;  // 如果上面不及时跳出循环则在这里改为(t >= INF / 2)
    else cout << t << endl;

return 0;
}
```

## kruskal

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 100;

structNode{
    int a, b, w;
  
    bool operator< (const Node &N) const {
        return w < N.w;
    }
}edges[N];

int n, m, res, cnt;
int g[N];

intfind(int a){
    if (a != g[a]) g[a] = find(g[a]);
    return g[a];
}

intkruskal(){
    for (int i = 0; i < m; i++) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
  
        a = find(a), b = find(b);  
        if (a != b) {
            g[a] = b;
            res += w;
            cnt++;
        }
    }
  
    if (cnt < n - 1) return -1;
    else return res;
}

intmain(){
    cin >> n >> m;
  
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }
    for (int i = 1; i <= n; i++) g[i] = i;
    sort(edges, edges + m);
  
    int t = kruskal();
    cout << t;
  
    return 0;
}
```

Last modification：February 7, 2023