. (论述题) 【要求：给出代码，并给出编译调试输出结果的截图】 Input 多组测试数据，对于每组数据， 第一行是两个整数，分别表示节点的数目M和边的数目N。 从第二行至第M+1行，每行三个整数，start, end, value. 分别表示节点start，end之间有一条长度为value.的边。 （M， N， start， end， value < 100) Output 对于每组输入数据，输出最小生成树的各边。 Sample Input 3 3 1 2 1 2 3 2 1 3 4 Sample Output (1,2)(2,3)

由于题目描述比较清晰，这里直接给出 Prim 算法的代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

int n, m;
int dis[MAXN];
bool vis[MAXN];
int g[MAXN][MAXN];

void prim() {
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[1] = 0;
    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (u == 0 || dis[j] < dis[u])) {
                u = j;
            }
        }
        vis[u] = true;
        if (i != 1) {
            cout << '(' << u << ',' << g[u][i] << ')';
        }
        for (int v = 1; v <= n; v++) {
            if (!vis[v] && g[u][v] < dis[v]) {
                dis[v] = g[u][v];
            }
        }
    }
}

int main() {
    while (cin >> n >> m) {
        memset(g, INF, sizeof(g));
        for (int i = 1; i <= m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            g[u][v] = g[v][u] = w;
        }
        prim();
        cout << endl;
    }
    return 0;
}

下面是一组输入输出的示例及解释：

输入：

3 3
1 2 1
2 3 2
1 3 4

输出：

(1,2)(2,3)

解释：输入表示有 3 个节点和 3 条边，根据输入生成的邻接矩阵如下：

  1 2 3
1 0 1 4
2 1 0 2
3 4 2 0

其中，0 表示同一个节点，INF 表示没有边相连。运行 Prim 算法，输出最小生成树的各边，其中 (1,2) 表示节点 1 和节点 2 之间有一条边，边权为 1，(2,3) 表示节点 2 和节点 3 之间有一条边，边权为 2。