最小生成树

Graph

template <typename T>
class graph {
public:
    struct edge {
        int from;
        int to;
        T cost;
    };

    const int n;
    std::vector<edge> edges;
    std::vector<std::vector<int>> g;

    graph(int _n) : n(_n), g(_n) {}

    virtual int add(int from, int to, T cost) = 0;
};

template <typename T>
class digraph : public graph<T> {
public:
    using graph<T>::edges;
    using graph<T>::g;
    using graph<T>::n;

    digraph(int _n) : graph<T>(_n) {}

    int add(int from, int to, T cost = 1) {
        assert(0 <= from && from < n && 0 <= to && to < n);
        int id = (int) edges.size();
        g[from].push_back(id);
        edges.push_back({from, to, cost});
        return id;
    }

    digraph<T> reverse() const {
        digraph<T> rev(n);
        for (auto &e : edges) {
            rev.add(e.to, e.from, e.cost);
        }
        return rev;
    }
};

template <typename T>
class undigraph : public graph<T> {
public:
    using graph<T>::edges;
    using graph<T>::g;
    using graph<T>::n;

    undigraph(int _n) : graph<T>(_n) {}

    int add(int from, int to, T cost = 1) {
        assert(0 <= from && from < n && 0 <= to && to < n);
        int id = (int) edges.size();
        g[from].push_back(id);
        g[to].push_back(id);
        edges.push_back({from, to, cost});
        return id;
    }
};

kruskal

struct DSU {
    std::vector<int> f, siz;
    int components = 0;

    DSU(int n) : f(n), siz(n, 1), components(n) {
        std::iota(f.begin(), f.end(), 0);
    }

    inline int find(int x) {
        while(x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        components--;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }

    int total_components() {
        return components;
    }
};

template <typename T>
std::vector<int> kruskal(const undigraph<T> &g, T& ans) {
    std::vector<int> order(g.edges.size());
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&g](int a, int b) {
        return g.edges[a].cost < g.edges[b].cost;
    });
    DSU d(g.n);
    std::vector<int> ans_list;
    ans = 0;
    for (int id : order) {
        auto &e = g.edges[id];
        if (!d.same(e.from, e.to)) {
            d.merge(e.from, e.to);
            ans_list.push_back(id);
            ans += e.cost;
        }
    }
    return ans_list;
    // returns edge ids of minimum "spanning" forest
}

prim

template <typename T>
bool prim(const undigraph<T> &g, T& ans) {
    std::vector<bool> vis(g.n);
    std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<std::pair<T, int>> > q;
    q.push({0, 0});
    int cnt = 0; ans = 0;
    while (!q.empty() && cnt < g.n) {
        T expected = q.top().first;
        int u = q.top().second; q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        ans += expected; cnt++;
        for (int id : g.g[u]) {
            auto &e = g.edges[id];
            int to = e.from ^ e.to ^ u;
            if (!vis[to]) {
                q.push({e.cost, to});
            }
        }
    }
    return cnt == g.n;
    // returns false if there's not connected
}

最后更新: 2024年1月2日 21:37:12
创建日期: 2024年1月2日 19:47:42