#include <stdio.h> #include <stdlib.h> #define MAXN 1005 #define INF 0x3f3f3f3f int n, m, ans = 0; int g[MAXN][MAXN], vis[MAXN], dis[MAXN]; void prim() { for (int i = 1; i <= n; i++) dis[i] = INF; 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] = 1; ans += dis[u]; for (int v = 1; v <= n; v++) if (!vis[v] && g[u][v] < dis[v]) dis[v] = g[u][v]; } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g[i][j] = INF; for (int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); g[u][v] = g[v][u] = w; } prim(); printf("%d\n", ans); return 0; }在该代码的基础上增加打印输出路线节点和两个节点的树边权值
时间: 2024-01-19 14:03:10 浏览: 25
在代码的prim函数中,每次更新dis数组时,可以记录下前驱节点pre[v],表示v节点在生成树中的前驱节点是pre[v]。在循环结束后,可以依次输出生成树中的边和节点。具体实现如下:
```
void prim() {
int pre[MAXN];
for (int i = 1; i <= n; i++) {
dis[i] = INF;
pre[i] = 0;
}
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] = 1;
ans += dis[u];
if (pre[u]) printf("%d -> %d: %d\n", pre[u], u, dis[u]);
for (int v = 1; v <= n; v++) {
if (!vis[v] && g[u][v] < dis[v]) {
dis[v] = g[u][v];
pre[v] = u;
}
}
}
for (int i = 1; i <= n; i++) if (pre[i]) printf("%d ", i);
printf("\n");
}
```
在主函数中,直接调用prim函数即可输出最小生成树的边和节点。