[ACM模块化模板]最小生成树-Kruskal

[ACM模块化模板]最小生成树-Kruskal

更好的阅读体验：http://www.abmcar.top/archives/template-kruskal

git仓库链接:https://github.com/abmcar/ACM/tree/master/template

template 
class Kruskal
{
public:
    int find(int x)
    {
        if (x == father[x])
            return x;
        father[x] = find(father[x]);
        return father[x];
    }
    Kruskal(int _n) : n(_n)
    {
        father.resize(n + 1);
        ans = 0;
        for (int i = 1; i <= n; i++)
            father[i] = i;
    }
    void insert(T x, T y, T z)
    {
        edges.push_back({x, y, z});
    }
    void solve()
    {
        sort(edges.begin(), edges.end());
        for (int i = 0; i < (int)edges.size(); i++)
        {
            int f1 = find(edges[i].from);
            int f2 = find(edges[i].to);
            if (f1 == f2)
                continue;
            ans += edges[i].val;
            father[f1] = f2;
            cnt++;
        }
    }
    int get()
    {
        if (cnt != n - 1)
            return -1;
        return ans;
    }

private:
    struct Edge
    {
        T from, to, val;
        bool operator<(Edge b) const
        {
            return val < b.val;
        }
    };
    vector edges;
    vector father;
    int n, cnt;
    T ans;
};

食用样例:

    int n, m;
    cin >> n >> m;
    //初始化构造
    Kruskal kru(n);
    for (int i = 1; i <= m; i++)
    {
        int t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        //插入新边
	kru.insert(t1, t2, t3);
    }
    //求解
    kru.solve();
    //获取结果
    if (kru.get() == -1)
        cout << "impossible" << endl;
    else
        cout << kru.get() << endl;