一个有 n 户人家的村庄，有 m 条路相互连接着。村里现在要修路，每条路都有一个成本价格，现在请你帮忙计算下，最少需要花费多少钱，就能让这 n 户人家连接起来。
每户之间可能有多条道路连接，但不可能自己与自己相连。
数据范围: 
， 
， 
进阶： 时间复杂度 )
， 空间复杂度 )
[编程题]最小生成树
用并查集实现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)
运行时间：44ms超过54.32% 用Python 3提交的代码
占用内存：6928KB超过1.23%用Python 3提交的代码
使用克鲁斯卡尔算法：
详见
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)
这个单纯想练习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)
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)
只能过两组样例……反复看都感觉自己的代码逻辑没有问题，想求大佬看看问题在哪里？
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
回复(0)
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)
很好奇，课本教了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)
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)
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)
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 返回最小的花费代价使得这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)
为什么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)
#include <queue>
#include <set>
#include <limits>
#include <vector>
struct edge {
int v, w;
}; //声明一个结构体，存儿子和边权
vector<edge> dp[5000];
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最小的花费代价使得这n户人家连接起来
* @param n int整型 n户人家的村庄
* @param m int整型 m条路
* @param cost int整型vector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
* @return int整型
*/
int d[5000];
int vis[5000];
int pre[5000];
priority_queue<pair<int, int>> q;
int ans = 0;
int cnt;
bool prim(int s, int n, set<int> points) {
//将所有点到源点的距离设置为无穷大
for (auto it = points.begin(); it != points.end(); it++) {
d[*it] = INT_MAX;
}
d[0] = INT_MAX; //哨兵
d[s] = 0;//源点到源点的距离为0；
for (auto it = points.begin(); it != points.end(); it++) { //遍历所有点
//选秀
int u = 0; //哨兵
//每次从圈内选一个距离最小的点u
for (auto itt = points.begin(); itt != points.end(); itt++) //遍历所有点
{
//如果在圈内
if (!vis[*itt] &&
d[*itt] < d[u]) u = *itt; //选出距离圈外距离最小的点
}
vis[u] = 1;//u已出圈
ans += d[u];
cout << "u:" << u << endl;
if (d[u] != INT_MAX) cnt++; //判断是否可以连通
//儿子们
for (auto ed : dp[u]) {
//将距离更新
int v = ed.v, w = ed.w;
cout << v << endl;
if (w < d[v]) {
d[v] = w;
}
}
//选秀
//推入源点：起始
// q.push({0,s});
// while(q.size())
// {
// auto t = q.top();
// q.pop();
// int u = t.second;
// //如果被扩展过了，就跳过
// if(vis[u]) continue;
// vis[u] = 1;
// // for(auto k:dp[u])
// // {
// // int v = k.v, w = k.w;//儿子和权重
// // //对所有出边执行松弛操作
// // if(d[v]>(d[u]+w))
// // {
// // d[v]=d[u]+w;
// // pre[v] = u;
// // q.push({-d[v],v});
// // }
// // }
// }
}
return cnt == n;
}
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
// write code here
set<int> points; //所有点的集合
//遍历所有边，存入图中 将第一个选为源点
dp[cost[0][0]].push_back({cost[0][1], cost[0][2]});
dp[cost[0][1]].push_back({cost[0][0], cost[0][2]}); //无向图，同步更新
for (int i = 1; i < m; i++) {
dp[cost[i][0]].push_back({cost[i][1], cost[i][2]});
dp[cost[i][1]].push_back({cost[i][0], cost[i][2]}); //无向图，同步更新
points.insert(cost[i][0]);
points.insert(cost[i][1]);
}
int cnt = prim(cost[0][0], n, points); //传入源点
cout << "cnt:" << cnt << endl;
return ans;
}
};
发表于 2023-10-19 17:15:48
回复(0)
c代码实现，主要影响是需要手写排序算法。
使用递归实现排序算法，可能导致栈溢出，使用栈实现要尽量加快循环遍历。
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最小的花费代价使得这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 <stdio.h>
#include <stdlib.h>
#include <string.h>
void swap(int* x, int* y) {
int z[3] = {0};
memcpy(z, x, 3 * sizeof(int));
memcpy(x, y, 3 * sizeof(int));
memcpy(y, z, 3 * sizeof(int));
}
typedef struct _Range {
int start, end;
} Range;
Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}
void quick_sort(int* arr[], const int len) {
if (len <= 0)
return; //避免len等于负值时错误
//r[]模拟堆疊,p为数量,r[p++]为push,r[--p]为pop且取得元素
Range r[len];
int p = 0;
r[p++] = new_Range(0, len - 1);
while (p) {
Range range = r[--p];
if (range.start >= range.end)
continue;
int mid = arr[range.end][2];
int left = range.start, right = range.end - 1;
while (left < right) {
while (arr[left][2] < mid && left < right)
left++;
while (arr[right][2] >= mid && left < right)
right--;
if(left<right){
swap(arr[left], arr[right]);
//加速设置，使代码尽快遍历完,否则超时
left++;
right--;
}
}
if (arr[left][2] > arr[range.end][2])
swap(arr[left], arr[range.end]);
else
left++;
r[p++] = new_Range(range.start, left - 1);
r[p++] = new_Range(left + 1, range.end);
}
}
int find(int* parent, int x) { //找到最高的父亲节点
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}
int miniSpanningTree(int n, int m, int** cost, int costRowLen,
int* costColLen ) {
// write code here
int* parent = (int*)malloc((n+10) * sizeof(int));
for (int i = 1; i <=n; i++) { //初始父亲设置为自己
parent[i] = i;
}
quick_sort(cost, costRowLen);//按边递增排序
int res = 0;
for (int i = 0; i < costRowLen;
i++) { //遍历所有边，连通的放入一个并查集
int x = cost[i][0];
int y = cost[i][1];
int z = cost[i][2];
int px = find(parent, x); //查找最上边父亲
int py = find(parent, y);
if (px != py) { //如果二者不在同一集合
res += z;
parent[px] = py; //设置最上边父亲相同
}
}
return res;
}
发表于 2023-07-20 15:03:38
回复(0)
有谁能帮忙看一下这个代码的错误在哪里吗？
#include <cstring>
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最小的花费代价使得这n户人家连接起来
* @param n int整型 n户人家的村庄
* @param m int整型 m条路
* @param cost int整型vector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
* @return int整型
*/
const int INF = 1e4+5;
const int cc = 5000+6;
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
// write code here
int minlost[cc];
int dot[cc];
int used[cc];
int maps[cc][cc];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
// cout<<"DD"<<endl;
maps[i][j]=INF;
}
}
for(int i=0;i<m;i++){
// cout<<cost[i][0]<<endl;
maps[cost[i][0]][cost[i][1]] = cost[i][2];
maps[cost[i][1]][cost[i][0]] = cost[i][2];
}
// cout<<maps[1][3];
for(int i=1;i<=n;i++){
minlost[i] = maps[1][i];
dot[i] = 1;
used[i] =0;
}
int sum =0;
used[1]=1;
for(int i=1;i<n;i++){
int pp=1;
for(int j=1;j<=n;j++){
if(!used[j] && minlost[j]<minlost[pp]) pp = j;
}
used[pp]=1;
sum+=minlost[pp];
for(int k=1;k<=n;k++){
if(!used[k] && minlost[k]>maps[pp][k]){
minlost[k] = maps[pp][k];
dot[k] =pp;
}
}
}
return sum;
}
};
发表于 2023-07-20 10:50:42
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-07 11:15:47
-
2023-02-16 17:16:29
-
2023-01-07 20:22:10
-
2022-12-29 08:17:06
-
2022-12-08 17:18:42
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
