ACM模版

描述

N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。

Input
第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000)
第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)

Output
输出最小生成树的所有边的权值之和。

Input示例
9 14
1 2 4
2 3 8
3 4 7
4 5 9
5 6 10
6 7 2
7 8 1
8 9 7
2 8 11
3 9 2
7 9 6
3 6 4
4 6 14
1 8 8

Output示例
37

题解

简单的最小生成树，使用Prim算法或者Kruskal算法均可，这里使用的是前者。

代码

#include <iostream>
#include <cstring>

using namespace std;

/* * Prim求MST * 耗费矩阵cost[][]，标号从0开始，0 ~ n－1 * 返回最小生成树的权值，返回-1表示原图不连通 */

const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
bool vis[MAXN];
int lowc[MAXN];
int cost[MAXN][MAXN];

// 修正cost（添加边）
void updata(int x, int y, int v)
{
    cost[x - 1][y - 1] = v;
    cost[y - 1][x - 1] = v;
    return ;
}

int Prim(int cost[][MAXN], int n)   // 0 ~ n - 1
{
    int ans = 0;
    memset(vis, false, sizeof(vis));
    vis[0] = true;
    for (int i = 1; i <= n; i++)
    {
        lowc[i] = cost[0][i];
    }
    for (int i = 1; i < n; i++)
    {
        int minc = INF;
        int p = -1;
        for (int j = 0; j < n; j++)
        {
            if (!vis[j] && minc > lowc[j])
            {
                minc = lowc[j];
                p = j;
            }
        }
        if (minc == INF)
        {
            return -1;  // 原图不连通
        }
        ans += minc;
        vis[p] = true;
        for (int j = 0; j < n; j++)
        {
            if (!vis[j] && lowc[j] > cost[p][j])
            {
                lowc[j] = cost[p][j];
            }
        }
    }
    return ans;
}

int main(int argc, const char * argv[])
{
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// #endif
    memset(cost, 0x3f, sizeof(cost));
    int N, M;
    cin >> N >> M;
    int S, E, W;
    for (int i = 0; i < M; i++)
    {
        cin >> S >> E >> W;
        updata(S, E, W);
    }
    cout << Prim(cost, N) << '\n';
    return 0;
}

参考

《最小生成树》