请帮我用c语言实现目标要求运用图论的相关方法！要求输入以下数据能得到期望输出：有n个城市需要建立货运路线每个城市之间的距离都已经确定你需要选择一些城市之间建立道路必须确保能够通过这些道路到达任意一个城市。现在你需要找到最小的建设成本并且保证任意两个城市之间都能通过这些道路到达。将每个城市看作图中的一个节点将每条道路看作连接两个节点的一条边边的权值即为两个节点之间的距离。然后使用最小生成树算法找到一

以下是使用Kruskal算法的代码实现：

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

#define MAX_N 100 #define MAX_M 1000

// 定义边的结构体 typedef struct { int u, v, w; } Edge;

// 定义并查集 int fa[MAX_N];

void initSet(int n) { for (int i = 0; i < n; i++) { fa[i] = i; } }

int findSet(int x) { if (fa[x] != x) { fa[x] = findSet(fa[x]); } return fa[x]; }

void unionSet(int x, int y) { int fx = findSet(x); int fy = findSet(y); if (fx != fy) { fa[fx] = fy; } }

// 定义边的比较函数，按边权从小到大排序 int cmp(const void* a, const void* b) { Edge* p = (Edge*)a; Edge* q = (Edge*)b; return p->w - q->w; }

// Kruskal算法求最小生成树 int kruskal(int n, int m, Edge* edges) { initSet(n); qsort(edges, m, sizeof(Edge), cmp); int cnt = 0; // 记录加入的边数 int ans = 0; // 记录总权值 for (int i = 0; i < m; i++) { int u = edges[i].u; int v = edges[i].v; int w = edges[i].w; if (findSet(u) != findSet(v)) { // 如果u,v不在同一集合中 unionSet(u, v); ans += w; cnt++; if (cnt == n - 1) { // 已经加入n-1条边，即构成了一棵生成树 break; } } } return ans; }

int main() { int n, m; Edge edges[MAX_M]; scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w); } int ans = kruskal(n, m, edges); printf("%d\n", ans); return 0;