鱼C论坛

 找回密码
 立即注册
查看: 48|回复: 1

[已解决]计算最小生成树权值

[复制链接]
发表于 2024-11-29 16:13:24 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本题要求采用prim算法求最小生成树,输出其权值之和

输入格式:
输入为顶点 顶点 权值,以 0 0 0表示结束

输出格式:
输出为最小生成树的权值大小

输入样例:
0 1 5
1 0 5
0 2 30
2 0 30
0 3 14
3 0 14
1 2 24
2 1 24
2 3 17
3 2 17
1 4 14
4 1 14
1 5 10
5 1 10
4 5 25
5 4 25
2 5 17
5 2 17
3 5 8
5 3 8
0 0 0
输出样例:
在这里给出相应的输出。例如:

54

这题用C或者C++怎么做
最佳答案
2024-11-29 16:13:38
这道题可以使用Prim算法来求解最小生成树(MST)的总权值。以下是一种使用C++实现Prim算法的示例代码:
#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

// 定义最大顶点数
#define MAXVEX 100

// 定义一个结构体来表示边
struct Edge {
    int src, dest, weight;
};

// 使用Prim算法计算最小生成树的权值
int primMST(vector<Edge>& edges, int V) {
    // 初始化邻接矩阵
    int graph[MAXVEX][MAXVEX];
    for (int i = 0; i < V; ++i)
        for (int j = 0; j < V; ++j)
            graph[i][j] = INT_MAX;
    
    for (auto& edge : edges) {
        graph[edge.src][edge.dest] = edge.weight;
        graph[edge.dest][edge.src] = edge.weight;
    }

    // store MST
    vector<bool> inMST(V, false);
    vector<int> key(V, INT_MAX);
    int res = 0;

    key[0] = 0;  // choose starting vertex

    for (int count = 0; count < V; ++count) {
        int u = -1;

        // 从未选择的顶点中选择权值最小的顶点
        for (int i = 0; i < V; ++i)
            if (!inMST[i] && (u == -1 || key[i] < key[u]))
                u = i;

        // 将选择的顶点加入MST
        inMST[u] = true;
        res += key[u];

        // 更新相邻的权值
        for (int v = 0; v < V; ++v)
            if (graph[u][v] != INT_MAX && !inMST[v] && graph[u][v] < key[v])
                key[v] = graph[u][v];
    }
    return res;
}

int main() {
    vector<Edge> edges;
    int src, dest, weight;

    // 读取输入
    while (cin >> src >> dest >> weight) {
        if (src == 0 && dest == 0 && weight == 0) break;
        edges.push_back({src, dest, weight});
    }

    // 在使用样例中,总的顶点数可以通过分析获取
    int V = 6; // 根据示例的数据,顶点数为6

    // 计算并输出MST的权值
    cout << primMST(edges, V) << endl;

    return 0;
}

这个代码片段实现了Prim的算法,并读取输入直到"0 0 0"为止。请根据您实际的问题情况调整此代码,以匹配特定情况下的输入格式和顶点数量。代码假设顶点编号从0开始,您可能需要根据实际场景进行调整。

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-11-29 16:13:38 | 显示全部楼层    本楼为最佳答案   
这道题可以使用Prim算法来求解最小生成树(MST)的总权值。以下是一种使用C++实现Prim算法的示例代码:
#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

// 定义最大顶点数
#define MAXVEX 100

// 定义一个结构体来表示边
struct Edge {
    int src, dest, weight;
};

// 使用Prim算法计算最小生成树的权值
int primMST(vector<Edge>& edges, int V) {
    // 初始化邻接矩阵
    int graph[MAXVEX][MAXVEX];
    for (int i = 0; i < V; ++i)
        for (int j = 0; j < V; ++j)
            graph[i][j] = INT_MAX;
    
    for (auto& edge : edges) {
        graph[edge.src][edge.dest] = edge.weight;
        graph[edge.dest][edge.src] = edge.weight;
    }

    // store MST
    vector<bool> inMST(V, false);
    vector<int> key(V, INT_MAX);
    int res = 0;

    key[0] = 0;  // choose starting vertex

    for (int count = 0; count < V; ++count) {
        int u = -1;

        // 从未选择的顶点中选择权值最小的顶点
        for (int i = 0; i < V; ++i)
            if (!inMST[i] && (u == -1 || key[i] < key[u]))
                u = i;

        // 将选择的顶点加入MST
        inMST[u] = true;
        res += key[u];

        // 更新相邻的权值
        for (int v = 0; v < V; ++v)
            if (graph[u][v] != INT_MAX && !inMST[v] && graph[u][v] < key[v])
                key[v] = graph[u][v];
    }
    return res;
}

int main() {
    vector<Edge> edges;
    int src, dest, weight;

    // 读取输入
    while (cin >> src >> dest >> weight) {
        if (src == 0 && dest == 0 && weight == 0) break;
        edges.push_back({src, dest, weight});
    }

    // 在使用样例中,总的顶点数可以通过分析获取
    int V = 6; // 根据示例的数据,顶点数为6

    // 计算并输出MST的权值
    cout << primMST(edges, V) << endl;

    return 0;
}

这个代码片段实现了Prim的算法,并读取输入直到"0 0 0"为止。请根据您实际的问题情况调整此代码,以匹配特定情况下的输入格式和顶点数量。代码假设顶点编号从0开始,您可能需要根据实际场景进行调整。

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-7 04:21

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表