kkogoro

最小生成树模板
最小生成树洛谷P3366Kruskal#include <iostream> #include <...
扫描右侧二维码阅读全文
09
2018/11

最小生成树模板

最小生成树

洛谷P3366

Kruskal

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>


const int MAXN = 5007;
const int MAXM = 200007;


struct Edge {
    int u, v, w;
    bool operator < (const Edge &tmp) const {
        return w < tmp.w;
    }
} e[MAXM];


namespace UNION {
    int fa[MAXN];
    inline void init() {
        memset(fa, -1, sizeof fa);
        return;
    }
    int get(int x) {
        return fa[x] < 0 ? x : fa[x] = get(fa[x]);
    }
    inline void merge(int x, int y) {
        x = get(x);
        y = get(y);
        if (x != y) {
            if (fa[x] < fa[y]) {
                fa[x] += fa[y];
                fa[y] = x;
            }
            else {
                fa[y] += fa[x];
                fa[x] = y;
            }
        }
        return;
    }
}


inline bool Kruskal(int n, int m, int &tot) {
    std::sort(e + 1, e + 1 + m);
    UNION::init();
    int cnt = 1;
    tot = 0;
    for (int i = 1; i <= m && cnt < n; ++i) {
        int u = e[i].u, v = e[i].v;
        u = UNION::get(u);
        v = UNION::get(v);
        if (u != v) {
            ++cnt;
            tot += e[i].w;
            UNION::merge(u, v);
        }
    }
    return cnt == n;
}


int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[i].u = u, e[i].v = v, e[i].w = w;
    }
    int tot = 0;
    if (Kruskal(n, m, tot) == false) {
        printf("orz\n");
    }
    else {
        printf("%d\n", tot);
    }
    return 0;
}

Prim

#include <iostream>
#include <set>
#include <cstdio>
#include <cstring>


const int MAXN = 5007;
const int MAXM = 200007;


struct Edge {
    int to, w, nextEdge;
} e[MAXM << 1];
int cntEdge, head[MAXN];
inline void addEdge(int u, int v, int w) {
    ++cntEdge;
    e[cntEdge].to = v, e[cntEdge].nextEdge = head[u], head[u] = cntEdge, e[cntEdge].w = w;
    return;
}


const int INF = 0x7FFFFFFF;
bool vis[MAXN];
int dis[MAXN];
typedef std::pair<int, int> PII;
std::set<PII, std::less<PII> > min_heap;
inline bool Prim(int n) {
    min_heap.clear();
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= n; ++i) {
        dis[i] = INF;
    }
    dis[1] = 0;
    min_heap.insert(PII(0, 1));
    int tot = 0;
    while (min_heap.empty() == false) {
        std::set<PII, std::less<PII> >::iterator top = min_heap.begin();
        int u = top->second;
        min_heap.erase(top);
        if (vis[u] == true) continue;
        vis[u] = true;
        ++tot;
        for (int it = head[u]; it != 0; it = e[it].nextEdge) {
            int v = e[it].to;
            if (vis[v] == false && dis[v] > e[it].w) {
                dis[v] = e[it].w;
                min_heap.insert(PII(dis[v], v));
            }
        }
    }
    return tot == n;
}


int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    if (Prim(n) == true) {
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans += dis[i];
        }
        printf("%d\n", ans);
    }
    else {
        printf("orz\n");
    }
    return 0;
}

杂谈

Kruskal适用于稀疏图,Prim使用于稠密图。

Last modification:November 9th, 2018 at 11:15 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment