题目描述 给出一个无向图，求出最小生成树，如果存在则打印最小生成树的边权之和，不存在则输入NO。 最小生成树：假设有 n 个点，则边应该有 n-1 条，而且各点到各点之间有通路。 数据范围 图的点数N 0<N<=5000 图的边数M 0<M<10^6 图的边权 d 输入格式 n m x1 y1 d1 x2 y2 d2 xm ym dm 输出格式 如果存在则打印最小生成树的边权之和，不存在则输出NO。 用C语言写一段程序

以下是使用 Prim 算法求解最小生成树的 C 语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 5000
#define MAX_M 1000000
#define INF 0x3f3f3f3f

typedef struct {
    int u, v, w;
} Edge;

Edge edges[MAX_M];
int head[MAX_N], dist[MAX_N], vis[MAX_N];

int cmp(const void* a, const void* b) {
    return ((Edge*)a)->w - ((Edge*)b)->w;
}

int main() {
    int n, m, u, v, w;
    scanf("%d%d", &n, &m);
    memset(head, -1, sizeof(head));
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        --u, --v;   // 将节点编号从 0 开始
        edges[i] = (Edge){u, v, w};
    }
    qsort(edges, m, sizeof(Edge), cmp);
    memset(vis, 0, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist));
    dist[0] = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int x = -1;
        for (int j = 0; j < n; ++j) {
            if (!vis[j] && (x == -1 || dist[j] < dist[x])) {
                x = j;
            }
        }
        if (x == -1 || dist[x] == INF) {    // 无法扩展，图不连通
            printf("NO\n");
            return 0;
        }
        vis[x] = 1;
        ans += dist[x];
        for (int j = head[x]; j != -1; j = edges[j].v) {
            int y = edges[j].u;
            if (!vis[y] && edges[j].w < dist[y]) {
                dist[y] = edges[j].w;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

程序先读入图的信息，将边按权值从小到大排序，然后从节点 0 开始，每次取出距离节点集合最近的未加入节点，将它加入节点集合，并更新与它相邻的未加入节点的距离。这样一直进行 n 次，直到节点集合包含所有节点，或者无法继续扩展，此时若节点集合包含所有节点，则输出最小生成树的边权之和，否则输出 NO。