最小生成（自用）

基本原理

总体上是贪心暴力的思想，不过根据枚举的对象不同分为两种方法：

prim算法

枚举对象是点。从起点开始枚举所有相邻的点，更新相应点的距离，找到距离起点最近的点，从该点继续枚举，然后继续更新，重复这个过程。似乎与dijstra算法很像，但是注意prim算法中点最多只能被更新一次，不会被重复更新，这样就能实现在一个连通图中找到连通所有点的最短路径了。

kruscal算法

枚举对象是边。将所有边信息存在结构体中，按权重从小到大排序，按顺序取边，若该边两点没有连通，则选择该边，否则，舍去该边。思路上较简单，但在代码比prim长（一般要用并查集、遍历、结构体）。

实现

prim

int prim()
{
    int res = 0; 
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        res += dist[t];
        st[t] = true;
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], w[t][j]);
    }
    return res;
}

kruscal

struct Edge
{
   int a, b, w;
    bool operator< (const Edge &t) const
    {
        return w < t.w;
    }
}e[M];
int p[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 0; i < m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        e[i] = {a, b, w};
    }
    sort(e, e + m);
    int res = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
        if (a != b)
        {
            p[a] = b;
            res = w;
        }
    }
    cout << n - 1 << ' ' << res << endl;
    return 0;
}

注意

prim一般只能处理一个连通图，但问题本身是多个连通分支时一般用kruscal
算法复杂度：prim O(v^2);kruscal O(eloge)