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;
}

Borůvka

这个板子如果有负权需要把返回值换成pair标记一下

#include <iostream>
#include <cstdio>


const int MAXN = 5007;
const int MAXM = 200007;
const int INF = 1e9;


struct Edge {
    int u, v, w;
} e[MAXM];
struct UNION {
    int fa[MAXN];
    inline void init(int n) {
        for (int i = 0; i <= n; ++i) fa[i] = -1;
        return;
    }
    int get(int x) {
        return fa[x] < 0 ? x : fa[x] = get(fa[x]);
    }
    inline int merge(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return 0;
        if (fa[x] < fa[y]) {
            fa[x] += fa[y];
            fa[y] = x;
        }
        else {
            fa[y] += fa[x];
            fa[x] = y;
        }
        return 1;
    }
} st;
int crossE[MAXN];
bool used[MAXM];
inline int Boruvka(int n, int m) {
    st.init(n);
    int ans = 0, merged = 0, cross_edge = 1;
    while (cross_edge) {
        cross_edge = 0;
        for (int i = 1; i <= n; ++i) crossE[i] = 0;
        for (int i = 1; i <= m; ++i) {
            if (used[i]) continue;
            int u = st.get(e[i].u), v = st.get(e[i].v), w = e[i].w;
            if (u == v) {
                used[i] = true;
                continue;
            }
            if (!crossE[u] || w < e[crossE[u]].w) crossE[u] = i;
            if (!crossE[v] || w < e[crossE[v]].w) crossE[v] = i;
        }
        for (int i = 1; i <= n; ++i) {
            int now = crossE[i];
            if (now && !used[now]) {
                used[now] = 1;
                ans += e[now].w;
                if (st.merge(e[now].u, e[now].v)) ++cross_edge, ++merged;
            }
        }
    }

    if (merged == n - 1) return ans;
    else return -1;
}


int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        e[i].u = x, e[i].v = y, e[i].w = z;
    }

    int ret = Boruvka(n, m);
    if (ret == -1) printf("orz\n");
    else printf("%d\n", ret);
    return 0;
}

杂谈

Kruskal适用于稀疏图,Prim使用于稠密图,Borůvka常用于解决特定问题

Last modification:June 30th, 2019 at 03:39 pm

Leave a Comment