算法标签：==贪心== ==图论==

Kruskal 算法思路

这个算法主要是运用了贪心思想。

首先对每个边进行排序，每次选取最小的边，用并查集判断是否选过或形成环。

当边选够了，输出。

注意事项

结束循环的条件有两种：

• ++ cnt >= n - 1：这时候注意 sum += edge[i].value 在判断的前面，因为判断的意义是：到现在为止，我又没有选够。
• ++ cnt >= n：这时候 sum += edge[i].value 在判断的后面，因为判断的意义是：如果选了这个，有没有超。

代码

#include <bits/stdc++.h>

using namespace std;
int f[1000005], n, m, cnt, sum;
struct G{
    int f, t, v;
} e[10000005];
bool cmp(G x, G y) {
    return x.v < y.v;
}
int find(int i) {
    if (f[i] == i) return i;
    else return f[i] = find(f[i]);
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        f[i] = i;
    }
    for (int i = 1; i <= m; i ++) {
        int x, y, z; cin >> x >> y >> z;
        e[i].f = x;
        e[i].t = y;
        e[i].v = z;
    }
    sort(e + 1, e + m + 1, cmp);
    for (int i = 1; i <= m; i ++) {
        // cout << e[i].f << " " << e[i].t << " " << e[i].v << "\n";
    }

    for (int i = 1; i <= m; i ++) {
        int x, y;
        x = e[i].f;
        y = e[i].t;
        x = find(x);
        y = find(y);
        if (x == y) continue;
        f[x] = y;

        if (++ cnt >= n) break;
        sum += e[i].v;
    }
    if (cnt < n - 1) cout << "orz";
    else cout << sum;
    return 0;
}

Prim 算法思路

定义 dis[i]为：生成完的点到所有点的最小距离。每次有新的节点生成完后更新一下就行。

每次找边权最短的比连接的那个点生成就行了。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, dis[1000005], a[105][105];

int main() {
    memset(dis, 0x7f, sizeof(dis));
    memset(a, 0x7f, sizeof(a));
    cin >> n >> m;

    for (int i = 1; i <= n; i ++)
        a[i][i] = 0;

    for (int i = 1; i <= m; i ++) {
        int x, y, z;
        cin >> x >> y >> z;
        a[x][y] = z;
        a[y][x] = z;
    }

    for (int i = 1; i <= n; i ++)
        dis[i] = a[1][i];

    int cnt = 1, sum = 0;
    int nw = 1;

//  for (int i = 1; i <= n; i ++) {
//      for (int j = 1; j <= n; j ++) {
//          printf("%10d ", a[i][j]);
//      }
//
//      cout << "\n";
//  }

    while (cnt < n) {
        int flag = 0;
        int minn = 1e9;

        for (int i = 1; i <= n; i ++) {
            if (dis[i] > 0) {
                if (minn > dis[i]) {
                    minn = dis[i];
                    flag = i;
                }
            }
        }

//      cout << flag << " " << minn << " " << nw << "\n";
        sum += minn;
        nw = flag;

        for (int i = 1; i <= n; i ++)
            dis[i] = min(dis[i], a[nw][i]);

        cnt ++;
    }

    cout << sum;
}