最小生成树_

害群之马

运行时间：44ms超过54.32% 用Python 3提交的代码

占用内存：6928KB超过1.23%用Python 3提交的代码

使用克鲁斯卡尔算法：

详见

http://data.biancheng.net/view/41.html

class Solution:
    def miniSpanningTree(self , n , m , cost ):
        cost=sorted(cost, key=lambda x: x[2] )
        ## tag 即为顶点的标记字典，可以通过顶点查询它的标记
        tag={  vtx : vtx  for vtx in range(1,n+1) }
        result=[]
        sum=0
        for u,v,w in cost:
            if (tag[u]!=tag[v]):
                ## u,v are not connected, choose this edge for construction
                result.append( [u,v,w] )
                temp=tag[v]
                for vtx in range(1,n+1):
                    if tag[vtx]==temp:
                        tag[vtx]=tag[u]
                sum+=w
                if(len(result)==n-1):
                    return sum
        return sum

编辑于 2021-06-23 16:10:18 回复(1)

C/C++

Yang67

这个单纯想练习Prim算法，但细节部分有bug，自己实在调试不出来，卡在了33,33%上，希望会的的大佬指点一下

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回最小的花费代价使得这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        //only return one value
 */
typedef struct
{
    int adjvex;
    int lowcost;
}close_edge;

int minimum(close_edge* closedge, int n)
{
    int i = 0;
    int index = -1;
    int min = 9000000;
    
    for (i = 1; i <= n; ++i)
        if (closedge[i].lowcost && min > closedge[i].lowcost)
        {
            min = closedge[i].lowcost;
            index = i;
        }
    
    return index;
}

int miniSpanningTree(int n, int m, int** cost, int costRowLen, int* costColLen ) {
    // write code here
    int* vexs = (int*)calloc(n + 1, sizeof(int));
    int i = 0;
    int j = 0;
    
    for (i = 1; i <= n; ++i)
        vexs[i] = i;
    
    int** Matrix = (int**)calloc(n + 1, sizeof(int *));
    for (i = 0; i < n + 1; ++i)
    {
        int* row = (int *)calloc(n + 1, sizeof(int));
        Matrix[i] = row;
    }
    
    for (i = 0; i < n + 1; ++i)
        for (j = 0; j < n + 1; ++j)
            Matrix[i][j] = 800000;
    
    for (i = 0; i < m; ++i)
        Matrix[cost[i][0]][cost[i][1]] = Matrix[cost[i][1]][cost[i][0]] = cost[i][2];
    
    close_edge* closedge = (close_edge *)calloc(n + 1, sizeof(close_edge));
    
    closedge[0].lowcost = 0;
    closedge[1].lowcost = 0;
    for (i = 2; i <= n; ++i)
    {
        closedge[i].adjvex = 1;
        closedge[i].lowcost = Matrix[1][i];
    }
    
    int count = 0;
    int k = -1;
    
    for (i = 1; i < n; ++i)
    {
        k = minimum(closedge, n);
        
        count += closedge[k].lowcost;
        
        closedge[k].lowcost = 0;
        
        for (j = 1; j <= n; ++j)
            if (Matrix[k][j] < closedge[j].lowcost)
            {
                closedge[j].adjvex = vexs[k];
                closedge[j].lowcost = Matrix[k][j];
            }
    }
    
    return count;
}

编辑于 2021-05-29 11:41:57 回复(3)

我也太菜了😭

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        if(n < 1 || m < 1 || cost == null) return 0;
        //参考地址：https://blog.csdn.net/qq_41754350/article/details/81460643
        //基本思想: 以边为主导地位，始终选择当前可用的最小边权的边(sort);
        //每次选择边权最小的边连接两个端点是kruskal的规则，并实时判断两个点之间有没有间接联通;
        Arrays.sort(cost, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[2] - b[2];//根据权值升序排列
            }
        });
        int minPath = 0;
        MinTree mt = new MinTree(n + 1);//节点从1开始
        for(int[] c : cost){
            if(mt.find(c[0]) != mt.find(c[1])){//没有直接或间接联通
                mt.union(c[0], c[1]);
                minPath += c[2];
            }
        }
        return minPath;
    } 
}

//最小生成树，借助并查集的知识
class MinTree{
    private int[] father;//属性，根
    
    public MinTree(int n){//构造器
        father = new int[n];
        for(int i = 0; i < n; i++){
            father[i] = i;
        }
    }
    
    //将x合并到y
    public void union(int x, int y){
        int xroot = find(x);
        int yroot = find(y);
        if(xroot == yroot) return;
        father[xroot] = yroot;
    }
    
    //查找根, 同时压缩路径
    public int find(int x){
        if(father[x] != x){
            father[x] = find(father[x]);
        }
        return father[x];
    }
}

发表于 2021-05-26 10:36:39 回复(0)

已注销

卡鲁斯卡尔 求最小生成树

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    int find(int x)//并查集合并及查找根节点
    {
        if(x !=p[x])
            p[x] = find(p[x]);
        return p[x];
    }
    int p[100010];
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        
        for(int i = 0; i <= n; i++) p[i] = i;//初始化并查集
        
        //排序
        sort(cost.begin(),cost.begin() + m, [](vector<int>& a, vector<int> &b){return a[2] < b[2];});
        int res = 0;
        for(int i = 0; i < m; i++)
        {
            if(find(cost[i][0]) != find(cost[i][1]))//如果不是同一个集合，
            {
                res += cost[i][2];//加路
                p[find(cost[i][0])] = find(cost[i][1]);//合并集合
            }
        }
        return res;       
    }
};

发表于 2021-03-29 23:54:47 回复(0)

飞天晴晴晴晴

int二维数组是干啥的？题我怎么看不懂

发表于 2021-03-19 21:04:20 回复(2)

Java

pein531

用并查集实现kruskal算法，并查集使用路径压缩和rank排序技巧进行加速

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        Arrays.sort(cost, (a, b) -> a[2] - b[2]);    // 先按边升序排列
        UnionFind uf = new UnionFind(n);
        int money = 0;
        for(int i = 0; i < m; i++){
            int from = cost[i][0] - 1;
            int to = cost[i][1] - 1;
            int costMoney = cost[i][2];
            if(!uf.isConnected(from, to)){
                uf.union(from, to);
                money += costMoney;
            }
            if(uf.getCount() == 1){
                // 所有节点已经连为一体了，退出循环
                break;
            }
        }
        return money;
    }
}

class UnionFind {
    private int[] parent;   // 每棵树的根节点
    private int[] rank;     // 每棵树的相对高度
    private int count;      // 连通分量数
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for(int i = 0; i < n; i++){
            parent[i] = i;
            rank[i] = 1;
        }
    }
    
    public int find(int x) {
        while(x != parent[x]){
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        // 两个节点根不相同时进行合并操作
        if(rootX != rootY){
            if(rank[rootX] > rank[rootY]){
                // x的树比y高，将y合并到x下
                parent[rootY] = rootX;
            }else if(rank[rootX] < rank[rootY]){
                // x的树比y矮，将x合并到y下
                parent[rootX] = rootY;
            }else{
                // 树一样高时合并顺序随意，但是合并另一个子树的树高度要改变
                parent[rootX] = rootY;
                rank[rootY] ++;
            }
        }
        count--;      // 缩减一个分量
    }
    
    // 判断两个节点的连通性
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);      // 比较根节点是否相同即可
    }
    
    // 返回连通分量数
    public int getCount() {
        return count;
    }
}

发表于 2021-12-12 09:27:10 回复(0)

C++

搬砖并快乐着

这题出的***，第一个测试样例默认往返权重一样，第二个测试样例往返权重不一样，用常规prim算法没法做

发表于 2021-07-29 11:31:31 回复(3)

C

枫_root

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回最小的花费代价使得这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整型
 */
int miniSpanningTree(int n, int m, int** cost, int costRowLen,
                     int* costColLen) {
    // 定义一个数组来存储每个顶点到已加入生成树的最近顶点的距离
    int homevexcost[n];
    // 定义一个邻接矩阵来存储各顶点之间的边的权重
    int edgecost[n][n];
    // 初始化最小生成树的总成本为0
    int sumcost = 0;
    int u = 0;
    int v = 0;
    int w = 0;

    // 初始化邻接矩阵中未连接的顶点间的权重为极大值（这里用32767表示）
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            edgecost[i][j] = 32765;
        }
    }

    // 根据给定的边和成本信息填充邻接矩阵
    for (int i = 0; i < costRowLen; i++) {
        u = cost[i][0] - 1;
        v = cost[i][1] - 1;
        w = cost[i][2];
        edgecost[u][v] = w;
        edgecost[v][u] = w; // 因为图是无向的
    }

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

    // 主循环来构建最小生成树
    for (int i = 1; i < n; i++) {
        // 寻找离已加入生成树的顶点集合最近的顶点及其成本
        int mincost = 32765;
        int l;
        for (int j = 0; j < n; j++) {
            if (homevexcost[j] != 0 && homevexcost[j] < mincost) {
                mincost = homevexcost[j];
                l = j;
            }
        }

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

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

    // 返回最小生成树的总成本
    return sumcost;
}

起初写的时候只考虑了往返权重一样，调式的时候用于生成网的邻接矩阵没有正确的赋值，赋值03 30 的时候11也赋值了，提交测试这个6,10,[[5,3,8],[1,3,6],[2,5,4],[2,3,5],[4,5,6],[3,4,3],[2,4,8],[1,2,2],[1,4,5],[5,6,2]]
案例时赋值时第一次循环没有赋值，后面几次循环的赋值对应的权重也不对。恳请各位大佬解救一下

发表于 2024-08-25 17:01:58 回复(1)

唐氏综合征

这道题的难点在于：如果有多个相互独立的环，不好判断并找出其环结构，如果只有一个的话，非常好处理，因此需要用到 Kruskal 算法，该算法的好处是可以合并所有元素到一个集合，使用最终指向同一个跟节点，这样我们在遍历的时候就不会出现一个独立的环状结构，对cost 排序再从最小开始加入路径，是用到贪心算法的思想，直到所有的村庄都被包含，则建造完成：

import java.util.*;

public class Solution {
    /**
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
     * @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */
    public int miniSpanningTree(int n, int m, int[][] cost) {
        Arrays.sort(cost, Comparator.comparingInt(a ->
                    a[2])); // 根据花费从小到大排序

        UnionFind uf = new UnionFind(n +
                                     1); // 创建并查集，注意顶点从1开始，所以大小为 n+1
        int minCost = 0;
        int edgesUsed = 0;

        for (int[] edge : cost) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];

            if (!uf.connected(u, v)) { // 如果u和v不在同一个集合
                uf.union(u, v); // 合并u和v所在的集合
                minCost += weight; // 累加成本
                edgesUsed++; // 使用的边数增加
                if (edgesUsed == n - 1)
                    break; // 如果已经使用了 n-1 条边，构成了最小生成树
            }
        }

        // 如果使用的边数不足 n-1，说明无法连接所有村庄
        return edgesUsed == n - 1 ? minCost : -1;
    }

    // 并查集类
    static class UnionFind {
        private final int[] parent;
        private final int[] rank;

        public UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int find(int p) {
            if (p != parent[p]) {
                parent[p] = find(parent[p]); // 路径压缩
            }
            return parent[p];
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP != rootQ) {
                if (rank[rootP] > rank[rootQ]) {
                    parent[rootQ] = rootP;
                } else if (rank[rootP] < rank[rootQ]) {
                    parent[rootP] = rootQ;
                } else {
                    parent[rootQ] = rootP;
                    rank[rootP]++;
                }
            }
        }

        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }
    }
}

发表于 2024-05-10 12:41:38 回复(0)

C++

牛客616798855号

class Edge

{

public:

int u;//起点

int v;//终点

int weight;//权重

Edge (int u=0,int v=0,int weight=0):u(u),v(v),weight(weight){}

bool operator<(const Edge& other)

{

return weight < other.weight;

}

};

class UnionFind {

private:

vector<int>parent;

public:

UnionFind(int n) :parent(n) {

for(int i=0;i<n;i++)

{

parent[i]=i;

}/*一根线连父节点和字节点，不算子节点*/

}

int Find(int x)

{

while(x!=parent[x])

{

x=parent[x];

}

return x;

}/*用whil写就有问题，它可能会一直死循环*/

void unite(int x, int y)

{

int rootX = Find(x);

int rootY = Find(y);

if (rootX != rootY) {

parent[rootX] = rootY;

}

};

int kruskal(int n, vector<Edge>& edges)

{

sort(edges.begin(), edges.end());

UnionFind uf(n);//只是代表有m个parent输出，代表的还是顶点

int sum=0;

for (const auto& edge : edges)

{

int u = edge.u;

int v = edge.v;

int rootX = uf.Find(u);

int rootY = uf.Find(v);

if (rootX != rootY)//不构成环，构成环的都去掉了

{

uf.unite(u, v);

sum+=edge.weight;

}

return sum;

}

class Solution {

public:

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* 返回最小的花费代价使得这n户人家连接起来

* @param n int整型 n户人家的村庄

* @param m int整型 m条路

* @param cost int整型vector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价

* @return int整型

*/

int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {

vector<Edge> edges(m);

int count=0;

for(const auto& k:cost)

{

edges[count].u=k[0];

edges[count].v=k[1];

edges[count].weight=k[2];

count++;

}

return kruskal(100000,edges);

}

};一个很有意思的玩意在这，你可以看到kruskal传了一个100000的参数，然后我就发现这个并查集它是有很多点没用上的，我一开始传的n,但这样数组越界了，那么我就想了，一根线一个父节点有m根线就有m个父节点，就算会有很多是重复的，但你没不能得出子、准确的解点数，就一定不可以小于m,所以只要传的参大于m就可以了

编辑于 2024-04-13 13:22:01 回复(0)

有点甜~

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
     int my_union[5505];
     int find_root(int x) {
        if(my_union[x] != x) {
            return  find_root(my_union[x]);
        }
        return x;
    }
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        int count=0;
        int aa,bb;
        int w=0;
       
        for(int i=0;i<n;i++) my_union[i+1]=i+1;
        sort(cost.begin(),cost.end(),[](vector<int> &a,vector<int> &b){return a[2] < b[2];});
        for(int i=0;i<m;i++)
        {
            aa=find_root(cost[i][0]);
            bb=find_root(cost[i][1]);
            if( aa!=bb )
            {
                my_union[bb]=aa;
                w=w+cost[i][2];
                count++;
            }
            if(count==n-1) break;
            
        }
        return w;
    }
};

发表于 2023-05-13 23:47:21 回复(0)

C++

改变眼泪的理由

只能过两组样例……反复看都感觉自己的代码逻辑没有问题，想求大佬看看问题在哪里？

class Solution {
public:
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        //使用Prim算法，从一个根节点来逐渐让树“长大”。
        //加入新节点时是从未加入树中的节点中搜索，因此不用担心构成回路。

        //记录这个节点的父节点是谁。同时也起到了标志该节点有没有被访问过的作用。
        vector<int> parent(n);
        vector<bool> flag(n);
        //记录这个点离S集，或者说离树的距离。只有与树的节点直接相邻的节点，才算可达。
        vector<int> dist(n);
        //缓存此轮循环中被加入的顶点的下标，视作为下一次循环时的父节点。
        int lastparent=0;
        //对所有节点初始化。
        for(int i=0;i<n;i++)
        {
            parent[i]=-1;
            dist[i]=INT_MAX;
            flag[i]=false;
        }
        dist[0]=0;
        flag[0]=true;
        //初始化树根的所有邻接点。
        for(auto edge:cost)
        {
            if( (edge[0]-1) ==0)
            {
                //将它们的父节点设置为树根
               parent[edge[1]-1]=0; 
               dist[edge[1]-1]=edge[2];
            }
        }
        int sum=0;
        
        while(1)
        {
            int mindistance=INT_MAX;
            int minindex=-1;
            //寻找出距离“树”最近的节点。根节点可以无视。
            for(int i=1;i<parent.size();i++)
            {    
                //如果还没被访问过
                //if(parent[i]==-1)
                if(flag[i]==false)
                {
                    if(dist[i]<mindistance)
                    {
                        mindistance=dist[i];
                        minindex=i;
                    }
                }
            }
            //如果所有的节点都被加入到树中了。
            if(minindex==-1)
            {
                break;
            }
            flag[minindex]=true;
            //将找到的节点的所有邻接点设为可达，即将它们的边值更新进dist数组。
            for(auto edge:cost)
            {
                //如果没被访问过
                if( (edge[0]-1) ==minindex && flag[edge[1]-1]==false)
                {
                    //它的邻接点的下标。
                    int adjoinIndex=edge[1]-1;
                    if(edge[2]<=dist[adjoinIndex])
                    {
                        dist[adjoinIndex]=edge[2];
                        parent[adjoinIndex]=minindex;
                    }
                }
            }
            sum+=dist[minindex];                
        }
        
        //构建树结束，现在遍历dist数组。来计算总的代价
        return sum;
    }
};

发表于 2022-08-18 21:52:47 回复(1)

Java

咚動凍东

import java.util.*;
public class Solution {
    int[] parent;
    int findParent(int i) {
        if(parent[i] == i) return i;
        parent[i] = findParent(parent[i]);
        return parent[i];
    }
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        parent = new int[n + 1];
        for(int i = 0; i <= n; i ++) {
            parent[i] = i;
        }
        Arrays.sort(cost, new Comparator<int[]>(){
            @Override
            public int compare(int[] p1,int[] p2) {
                return p1[2] - p2[2];
            }
        });
        int w = 0;
        for(int i = 0; i < m; i ++) {
            int a = cost[i][0];
            int b = cost[i][1];
            int p1 = findParent(a);
            int p2 = findParent(b);
            if(p1 != p2) {
                w = w + cost[i][2];
                parent[p2] = p1;
            }
        }
        return w;
    }

}

发表于 2022-03-23 10:59:00 回复(0)

C++

7.起床

#include <climits>

#include <vector>

class Solution {

public:

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* 返回最小的花费代价使得这n户人家连接起来

* @param n int整型 n户人家的村庄

* @param m int整型 m条路

* @param cost int整型vector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价

* @return int整型

*/

int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {

vector<vector<int> > grid(n + 1, vector<int>(n + 1, 10001));

for (int i = 0; i < m; i++) {

grid[cost[i][0]][cost[i][1]] = cost[i][2];

grid[cost[i][1]][cost[i][0]] = cost[i][2];

}

vector<int> minDist(n + 1, 10001);

vector<bool> inTree(n + 1, false);

minDist[1] = 0; // Start from vertex 1

for (int i = 1; i <= n; i++) {

int cur = -1;

int minval = INT_MAX;

for (int j = 1; j <= n; j++) {

if (!inTree[j] && minDist[j] < minval) {

minval = minDist[j];

cur = j;

}

if (cur == -1) break; // No more vertices to add

inTree[cur] = true; // Mark the current vertex as in the tree

for (int k = 1; k <= n; k++) {

if (!inTree[k] && grid[cur][k] < minDist[k]) {

minDist[k] = grid[cur][k];

}

int res = 0;

for (int i = 1; i <= n; i++) {

res += minDist[i];

}

return res;

}

};

有没有佬知道我这哪里错了，只能过6/8的用例

发表于 2024-08-30 11:23:49 回复(1)

nroney

注意输入案例中存在同一个边权重不一样的情况，使用prim算法注意取权重较小的值来构造图。

 for (int i = 0; i < m; i++) {
            if (cost[i][2] < graph[cost[i][0]][cost[i][1]]) {
                graph[cost[i][0]][cost[i][1]] = cost[i][2];
                graph[cost[i][1]][cost[i][0]] = cost[i][2];
            }
        }

发表于 2024-05-09 17:19:41 回复(0)

牛客76165061号

很好奇，课本教了Prime，但是实现起来比kruskal麻烦多了，意义是什么

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回最小的花费代价使得这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整型
 */

int Find(int *A, int i){
    if(A[i]==i) return i;
    else return A[i] = Find(A, A[i]);
}

void Union(int *A, int i, int j){
    A[Find(A, j)] = A[Find(A, i)];
}

void SetArr3(int *dest, int* src){
    dest[0] = src[0];
    dest[1] = src[1];
    dest[2] = src[2];
}

void ShellSort(int **cost, int lenc){
    int nextc[3], j;
    for(int m = lenc/2;m>=1;m/=2){
        for(int i=m;i<lenc;i++){
            SetArr3(nextc, cost[i]);
            for(j=i; (cost[j-m][2]>nextc[2])&&(j-m>=0);j-=m){
                SetArr3(cost[j], cost[j-m]);
            }
            SetArr3(cost[j], nextc);
        }
    }
}

int miniSpanningTree(int n, int m, int** cost, int costRowLen, int* costColLen ) {
    // shellsort O(mlogm)
    ShellSort(cost, m);
    // 并查集 O(n), 查询接近O(1)
    int arr[n];
    int sumcost = 0;
    for(int i=0;i<n;i++) arr[i] = i;

    // kruskal O(m)
    for(int i=0;i<m;i++){
        if(Find(arr, cost[i][1]-1)!=Find(arr, cost[i][0]-1)){
            Union(arr, cost[i][1]-1, cost[i][0]-1);
            sumcost += cost[i][2];
        }
    }
    return sumcost;
}

编辑于 2024-03-04 17:44:13 回复(0)

牛客2024007号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
     * @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */
    class UnionSet {
            private int nodeNum;
            private int[] parent;
            UnionSet(int num) {
                this.nodeNum = num;
                parent = new int[nodeNum];
                for(int i = 0; i < nodeNum; i++) {
                    parent[i] = i;
                }
            }

            public void union(int i, int j) {
                parent[find(i)] = find(j);
            }

            public int find(int i) {
                if(parent[i] != i) {
                    parent[i] = find(parent[i]);
                }
                return parent[i];
            }
        }
    
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        // 并查集
        Arrays.sort(cost, (a, b) -> {
            return a[2] - b[2];
        });
        UnionSet unionSet = new UnionSet(n + 1);
        int res = 0;
        for(int []list: cost) {
            if(unionSet.find(list[0]) != unionSet.find(list[1])) {
                unionSet.union(list[0], list[1]);
                res += list[2];
            }
        }
        return res;
        

    }
}

编辑于 2024-02-05 21:05:20 回复(0)

牛客212561046号

Krusal+并查集

#include <algorithm>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
     * @param cost int整型vector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */
    
    vector<vector<int>> uset;

    int find(int u){
        if(u==uset[u][0]) return u;
        return find(uset[u][0]);
    }

    void unio(int u, int v){
        int rootu = find(u);
        int rootv = find(v);
        if(rootu!=rootv){
            if(uset[rootu][1]>uset[rootv][1]){
                uset[rootv][0] = rootu;
            }else if(uset[rootu][1]<uset[rootv][1]){
                uset[rootu][0] = rootv;
            }else{
                uset[rootu][0] = rootv;
                uset[rootu][1]++;
            }
        }
    }

    static bool cmp(vector<int> &a, vector<int> &b){
        return a[2]<b[2];
    }

    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        uset = vector<vector<int>>(n+1,vector<int>(2));
        sort(cost.begin(),cost.end(), cmp);
        int ans = 0;
        for(int i=1; i<=n; i++){
            uset[i][0] = i;
            uset[i][1] = 1;
        }
        for(int i=0; i<m; i++){
            int u = cost[i][0], v = cost[i][1];
            if(find(u)!=find(v)){
                ans += cost[i][2];
                unio(u,v);
            }
        }
        return ans;
    }
};

发表于 2023-12-26 18:29:43 回复(0)

kuangk

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回最小的花费代价使得这n户人家连接起来
# @param n int n户人家的村庄
# @param m int m条路
# @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
# @return int
#
class UnionFind:
    def __init__(self,n):
        self.parent=list(range(n))
        self.partN=n 
    def find(self,x):
        if self.parent[x]!=x:
            self.parent[x]=self.find(self.parent[x])
        return self.parent[x]    
    def union(self,x,y):
        Ix=self.find(x)
        Iy=self.find(y)
        if Ix!=Iy:
            self.parent[Ix]=Iy
            self.partN-=1
            return True
        return False
class Solution:
    def miniSpanningTree(self , n , m , cost ):
        cost.sort(key=lambda x:x[2])
        ans=0
        uf=UnionFind(n)
        for x in cost:
            if uf.partN!=1:
                if uf.union(x[0]-1,x[1]-1):
                    ans+=x[2]
            else: 
                break
        return ans

编辑于 2023-12-18 20:55:56 回复(0)

Java

菜鸟入门人

为什么prim算法通过不了，只能过前六个测试，不知道问题出哪里了 public int miniSpanningTree(int n, int m, int[][] cost) {

        int[][] graph = new int[n][n];

        //构建邻接矩阵图
        for (int i = 0; i < m; i++) {
            int u = cost[i][0] - 1;
            int v = cost[i][1] - 1;
            int weight = cost[i][2];
            graph[u][v] = weight;
            graph[v][u] = weight;
        }


        if (n == 2) return cost[0][2];
        // write code here
        //status数组记录节点是否联通了，初始化都为false
        boolean[] status = new boolean[n];
        Arrays.fill(status, false);
        //distance数组记录各个点到联通部分的最短距离,初始化无穷
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        //pre数组记录节点和谁联通,初始化都为-1
        int[] pre = new int[n];
        Arrays.fill(pre, -1);

        //开始遍历，n个点需要遍历n-1次，从点0（下标）开始
        dist[0] = 0;
        int totalCost = 0;
        for (int i = 0; i < n; i++) {//循环次数为点的个数，因为每个点都要加入mst
            // 选择键值最小的顶点u，它尚未包含在MST中
            int u = -1;//初始化该点为不连通（可能没必要？）
            int max = Integer.MAX_VALUE;//初始化一个值为整型最大值来循环排除无穷不可达
            for (int j = 0; j < n; j++) {
                if (!status[j] && dist[j] < max) {
                    max = dist[j];//这里不能忘记更新
                    u = j;
                }
            }
            //找到相应点，添加到集合
            if (u == -1) break;
            status[u] = true;
            totalCost += dist[u];
            for (int v = 0; v < n; v++) {
                if (!status[v] && graph[u][v] != 0 && graph[u][v] < dist[v]) {
                    pre[v] = u;
                    dist[v] = graph[u][v];
                }
            }
        }
        return totalCost;
    }

发表于 2023-11-29 11:48:22 回复(0)

最小生成树

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题