题目描述

解答 最小生成树模板

算法1

prim

C++ 代码

// poj1251.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 300;
const int INF = 0x3f3f3f3f;


int pointNum = 0;
int edgeCnt = 0;

int g[N][N];

int dist[N];
int st[N];


int prim()
{
    int ret = 0;

    memset(dist, 0x3f, sizeof dist);

    for (int i = 0; i < pointNum; i++)
    {
        int t = -1;

        for (int j = 1; j <= pointNum; j++) {
            if (st[j] == 0 && (t == -1 || dist[t] > dist[j])) {
                t = j;
            }
        }

        if (i != 0 && dist[t] == INF) return INF;
        if (i != 0) ret += dist[t];
        st[t] = 1;
        for (int j = 1; j <= pointNum; j++) dist[j] = min(dist[j], g[t][j]);
    }

    return ret;
}

int main()
{
    cin >> pointNum;
    while (pointNum != 0) {
        memset(g, 0x3f, sizeof(g));
        memset(st, 0, sizeof st);
        for (int loop = 1; loop < pointNum; loop++) {
            char c; int num;
            cin >> c; cin >> num;
            int idx = c - 'A' + 1;

            for (int i = 0; i < num; i++) {
                char to; int val;
                cin >> to >> val;
                int toIdx = to - 'A' + 1;
                g[idx][toIdx] = g[toIdx][idx] = min(val, g[idx][toIdx]);
            }
        }

        cout << prim() << endl;

        cin >> pointNum;
    }
}

算法2

kruscal

C++ 代码

// poj1251.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 300;
const int INF = 0x3f3f3f3f;
int dist[N];
int s[N];
int f[N];

struct EDGE {
    int a, b, w;
}edge[N];

int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

int n, m;
int pointNum;
int edgeCnt = 0;
bool cmp(const struct EDGE& a, const struct EDGE& b)
{
    return a.w < b.w;
}

int kruscal()
{
    int ret = 0; int cnt = 0;
    sort(edge, edge + edgeCnt, cmp);
    for (int i = 1; i <= pointNum;i++) f[i] = i;
    for (int i = 0; i < edgeCnt; i++) {
        int a = edge[i].a; int b = edge[i].b; int w = edge[i].w;
        a = find(a); b = find(b);
        if (a != b) {
            f[a] = b;
            ret += w;
            cnt++;
        }
    }
    if (cnt< pointNum - 1) return INF;

    return ret;
}

int main()
{
    cin >> pointNum;
    while (pointNum != 0) {
        edgeCnt = 0;
        for (int loop = 1; loop < pointNum; loop++) {
            char c; int num;
            cin >> c; cin >> num;
            int idx = c - 'A' + 1;

            for (int i = 0; i < num; i++) {
                char to; int val;
                cin >> to >> val;
                int toIdx = to - 'A' + 1;
                edge[edgeCnt].a = idx;
                edge[edgeCnt].b = toIdx;
                edge[edgeCnt].w = val;
                edgeCnt++;
            }
        }

        cout << kruscal() << endl;

        cin >> pointNum;
    }
}