最小生成树

kruskal

Kruskal 算法

#include <bits/stdc++.h>//kruskal算法
using namespace std;
#define int long long
int n, m, ans = 0;
int u, v, cnt = 0;
struct edge
{
    int x, y, val;
} a[200010];
int f[200010];
int find(int x)
{
    // while(x!=f[x])
    //     x = f[x] = f[f[x]];
    // return x;
    if (f[x] == x)
        return x;
    return f[x] = find(f[x]);
}
void kruskal()
{
    for (int i = 1; i <= m; i++)
    {
        u = find(a[i].x);
        v = find(a[i].y);
        if (u == v)
            continue;
        ans += a[i].val;
        f[u] = v;
        if (++cnt == n - 1)
            break;
    }
}
int cmp(edge a, edge b)
{
    return a.val < b.val;
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        f[i] = i;
    for (int i = 1; i <= m; i++)
        cin >> a[i].x >> a[i].y >> a[i].val;
    sort(a + 1, a + 1 + m, cmp);
    kruskal();
    if (cnt != n - 1)
        cout << "orz" << endl;
    else
        cout << ans << endl;
}

Prim 算法

1 朴素的 prim 算法

#include<bits/stdc++.h>//朴素的prim算法
using namespace std;
const int N = 5010, INF = 0x3f3f3f3f;
int g[N][N];
int dis[N]; 
bool vis[N];
int n, m;

int prim()
{
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0; //随便从一个起点开始
    int num = n, res = 0;
    while (num--)
    {              //对于连通图，必须要循环n次才能到所有顶点，获得最小生成树，非连通图会中途break
        int t = 0; //结点是从1开始的，t=0，此时说明还没开始待选
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && (!t || dis[i] < dis[t]))
                t = i;
        }
        if (dis[t] == INF)
            return -1; //存在顶点不可达，说明是不存在生成树
        vis[t] = true; //否则，顶点t加入集合
        res += dis[t]; //计算生成树的代价,第一次循环时必为事先初始化的1号顶点，dis为0，相当于不加
        //开始更新到集合(顶点t)的距离
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && dis[i] > g[t][i])
                dis[i] = g[t][i];
            //"只更新不在集合中的点，维护dis数组的含义，所以dis[t]不会被更新，就算自环是负值也不会被更新。"
        }
    }
    return res; //返回最小生成树的代价
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);
    int a, b, c;
    while (m--)
    {
        scanf("%d%d%d", &a, &b, &c);         
        g[a][b] = g[b][a] = min(g[a][b], c); 
    }
    int t = prim();
    t == -1 ? puts("orz") : printf("%d", t);

    return 0;
}

2 堆优化版

Prim 堆优化版

#include<bits/stdc++.h>//prim堆优化版
using namespace std;
typedef pair<int, int> PII; //<距离，顶点>
priority_queue<PII, vector<PII>, greater<PII>> heap;
const int N = 5010, M = 2e5 + 10; //无向图，边数要乘2
int h[N], e[M], w[M], ne[M], idx;
int dis[N];
bool vis[N]; //判断是否已经加入生成树的集合
int n, m;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int prim()
{
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    heap.push({dis[1], 1}); //本来还应该剩下的顶点都放进去，然后进行更新就行了，但是stl中的堆不能实现按关键字更新，
    int num = n, res = 0;   //用插入代替更新，所以，剩下的点就不放入了，更新到时再放入
    while (heap.size() && num)
    { //这里为什么这么写,原因同dijkstra
        auto t = heap.top();
        heap.pop();
        int v = t.second, d = t.first;
        //"此时取出的d必不可能是INF，因为前面加入堆的原因就是它被更新过" 
        if (vis[v]) continue; //如果v已经在生成树中了，本次循环无效，开始下一次，后面不再执行
        vis[v] = true, res += d, num--;                                                      //否则，加入生成树
        //修改未在生成树中的点到集合的最短距离
        for (int i = h[v]; i != -1; i = ne[i])
        {
            int j = e[i]; // v->e[i]的边,权值为w[i]
            if (!vis[j] && dis[j] > w[i])
                dis[j] = w[i], heap.push({dis[j], j});
        }
        //"只有当v到其它顶点可达或者距离更小，才会更新，因此每次取出的d都不是INF,当都不可达时，队列就为null了"
    }
    //"判断是因为什么原因退出？是因为堆空，还是有效循环num次完了"
    //"因为堆空退出说明图是非连通图，存在不可达点,此时num>0;但是如果num==0，说明已经得到了生成树。" 
    return num? -1: res;
}

int main()
{
    memset(h, -1, sizeof h);
    //"切记，邻接表存储时要初始化h数组" 
    scanf("%d%d", &n, &m);
    int a, b, c;
    while (m--)
    {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    int t = prim();
    t == -1 ? puts("impossible") : printf("%d", t);

    return 0;
}