题解 | #最小生成树#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回最小的花费代价使得这n户人家连接起来
 * @param n int整型 n户人家的村庄
 * @param m int整型 m条路
 * @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
 * @param costRowLen int cost数组行数
 * @param costColLen int* cost数组列数
 * @return int整型
 */
#include <stdlib.h>
#include <limits.h> // For INT_MAX

int miniSpanningTree(int n, int m, int** cost, int costRowLen,
                     int* costColLen) {
    int* homevexcost = malloc(n * sizeof(int)); // 存储到最近村庄的距离
    int** edgecost = malloc(n * sizeof(int*));  // 邻接矩阵
    int sumcost = 0; // 最小生成树的总成本

    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        edgecost[i] = malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            edgecost[i][j] = (i == j) ? 0 :
                             INT_MAX; // 对角线设为0，其余设为无穷大
        }
    }

    // 填充邻接矩阵
    for (int i = 0; i < costRowLen; i++) {
        int u = cost[i][0] - 1;
        int v = cost[i][1] - 1;
        int w = cost[i][2];
        if (w < edgecost[u][v]) {
            edgecost[u][v] = w;
            edgecost[v][u] = w;
        } // 因为图是无向的,if考虑到同一边有不同权值，取最小权值构建网
    }

    // 初始化第一个村庄的成本为0
    homevexcost[0] = 0;
    // 计算从第一个村庄出发到其他村庄的最短距离
    for (int i = 0; i < n; i++) {
        homevexcost[i] = edgecost[0][i];
    }

    // 构建最小生成树
    for (int i = 1; i < n; i++) {
        int mincost = INT_MAX;
        int l = -1;
        for (int j = 0; j < n; j++) {
            if (homevexcost[j] != 0 && homevexcost[j] < mincost) {
                mincost = homevexcost[j];
                l = j;
            }
        }

        // 更新已加入生成树的村庄集合，并累加当前边的成本到总成本中
        sumcost += mincost;
        homevexcost[l] = 0;

        // 更新从新加入的村庄出发到其他村庄的距离
        for (int a = 0; a < n; a++) {
            if (edgecost[l][a] < homevexcost[a]) {
                homevexcost[a] = edgecost[l][a];
            }
        }
    }

    // 释放内存并返回最小生成树的总成本
    for (int i = 0; i < n; i++) {
        free(edgecost[i]);
    }
    free(edgecost);
    free(homevexcost);

    return sumcost;
}