当前位置： 首页 > article >正文

08-图7 公路村村通（C）

article 2025/1/17 22:05:32

很明显聪明的同学已经发现，这是一个稠密图，所以用邻接矩阵。可以很好的表达，比邻接表有优势，所以，采用邻接矩阵破题，

当然也可以用邻接表，仔细观察我的AC,会发现其实都一样，只是存储形式不一样罢了。

很明显，这是一个最小生成树问题，也可以认为贪心算法，接下来我将分别展示两个实现路径，第一个 prim 算法， 第二个kruskal算法。

 第一个 prim 算法，哈哈，原来是我最开始搞错方向了，并未理解prim算法，这下也是让我印象深刻了。

测试点提示内存(KB)用时(ms)结果得分
0sample换数字，各种回路判断1924

答案正确

15 / 15
1M<N-1，不可能有生成树1924

答案正确

2 / 2
2M达到N-1，但是图不连通1924

答案正确

2 / 2
3最大N和M，连通42848

答案正确

5 / 5
4最大N和M，不连通41607

答案正确

6 / 6

 第二个kruskal算法，实际应用很简单，果然馒头嚼碎也不见得好吸收，一点点啃食的过程，也是非常锻炼计算思维。

按道理来说，应该是kruskal算法快，但是也就一个O(N^2) 与O(NlogN),可以看出来在1000个数据点（最大N(1000),M(3000)）下，区别还是有的。

测试点提示内存(KB)用时(ms)结果得分
0sample换数字，各种回路判断1884

答案正确

15 / 15
1M<N-1，不可能有生成树1884

答案正确

2 / 2
2M达到N-1，但是图不连通1884

答案正确

2 / 2
3最大N和M，连通41567

答案正确

5 / 5
4最大N和M，不连通41606

答案正确

6 / 6

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:

输入数据包括城镇数目正整数 n（≤1000）和候选道路数目 m（≤3n）；随后的 m 行对应 m 条道路，每行给出 3 个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从 1 到 n 编号。

输出格式:

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出 −1，表示需要建设更多公路。

输入样例:

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例:

12

 第一个 prim 算法，我的AC：

采用了，最小堆 + prim,.

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
 
#define MaxVertex 1001
#define INFITY 100001
#define MinValue -1
 
typedef struct ENode *Edge;
struct ENode{
	int V1, V2;
	int Weight;
};
 
typedef struct GNode *MGraph;
struct GNode{
	int Nv;
	int Ne;
	int G[MaxVertex][MaxVertex];
};
 
typedef struct Sign_Dist_VNode DistNode;
struct Sign_Dist_VNode{
	int V;
	int Weight;
};
 
typedef struct Heap *MinHeap;
struct Heap{
	DistNode *Data;
	int Size;
};
 
MGraph Build_Graph();
MGraph Init_Graph();
void Insert_Graph(MGraph M, Edge E);
MinHeap Init_Heap(int N);
void Creat_Heap(MGraph M, MinHeap H, int Vertex, bool* Visited, bool *collected);
void Push_Heap(MinHeap H, int index, int Weight, bool *collected);
void Counterpoise_Heap(MinHeap H, int index, int V, int Weight);
bool IsEmpty_Heap(MinHeap H);
DistNode Pop_Heap(MinHeap H, bool *collected);
void Prim(MGraph M, MinHeap H, bool* Visited, int *dist);
void Print_Result(int N, int *dist, bool* Visited);
 
int main()
{
	MGraph M;
	MinHeap H;
	int *dist;
	bool *Visited;
	M = Build_Graph();
	H = Init_Heap(M ->Nv);
	dist = (int*)malloc(sizeof(int) * M ->Nv);
	Visited = (bool*)calloc(M ->Nv, sizeof(bool));
	Prim(M, H, Visited, dist);
	Print_Result(M ->Nv, dist, Visited);
	return 0;
}
 
void Prim(MGraph M, MinHeap H, bool* Visited, int *dist)
{
	int j;
	bool *collected;
	collected = (bool*)calloc(M ->Nv, sizeof(bool));
	for(j = 1; j < M ->Nv; j++){
		dist[j] = M ->G[0][j];
	}
	DistNode Data;
	Creat_Heap(M, H, 0, Visited, collected);
	Visited[0] = true;
	dist[0] = 0;
	while(Data = Pop_Heap(H, collected), Data.Weight > 0){
		Visited[Data.V] = true;
		for(j = 0; j < M ->Nv; j++){
			if(!Visited[j] && M ->G[Data.V][j] < INFITY && (dist[j] > M ->G[Data.V][j])){
				dist[j] = M ->G[Data.V][j];
				Push_Heap(H, j, dist[j], collected);
				//有人会问，这样不会产生数据重复吗，注意Visited,遵循一次访问原则。
			}
		}
	}
}
void Print_Result(int N, int *dist, bool* Visited)
{
	int i, cost = 0;
	for(i = 0; i < N; i++){
		if(!Visited[i]){
			printf("-1\n");
			return ;
		}
		cost += dist[i];
	}
	printf("%d\n", cost);
	return ;
}
MGraph Build_Graph()
{
	MGraph M;
	Edge E;
	M = Init_Graph();
	E = (Edge)malloc(sizeof(struct ENode));
	for(int i = 0; i < M ->Ne; i++){
		scanf("%d %d %d", &E ->V1, &E ->V2, &E ->Weight);
		E ->V1 --; E ->V2 --;
		Insert_Graph(M, E);
	}
	return M;
}
MGraph Init_Graph()
{
	MGraph M;
	M = (MGraph)malloc(sizeof(struct GNode));
	scanf("%d %d", &M ->Nv, &M ->Ne);
	for(int i = 0; i < (M ->Nv); i++){
		for(int j = 0; j < (M ->Nv); j++){
			M ->G[i][j] = INFITY;
		}
	}
	return M;
}
void Insert_Graph(MGraph M, Edge E)
{
	M ->G[E ->V1][E ->V2] = E ->Weight;
	M ->G[E ->V2][E ->V1] = E ->Weight;
}
 
void Creat_Heap(MGraph M, MinHeap H, int Vertex, bool* Visited, bool *collected)
{
	for(int j = 0; j < M ->Nv; j++){
		if(M ->G[Vertex][j] < INFITY && !Visited[j]){
			Push_Heap(H, j, M ->G[Vertex][j], collected);
		}
	}
}
MinHeap Init_Heap(int N)
{
	MinHeap H;
	H = (MinHeap)malloc(sizeof(struct Heap));
	H ->Data = (DistNode*)malloc(sizeof(DistNode) * (N + 1));
	H ->Data[0].Weight = MinValue;
	H ->Size = 0;
	return H;
}
void Push_Heap(MinHeap H, int index, int Weight, bool *collected)
{
	int i;
	if(collected[index]){
		for(i = 1; i <= H ->Size; i++){
			if(index == H ->Data[i].V){
					H ->Data[i].Weight = Weight;
					Counterpoise_Heap(H, index, i, Weight);
					return ;
			}
		}
	}else{
		i = ++(H ->Size);
		Counterpoise_Heap(H, index, i, Weight);
		collected[index] = true;
		return ;
	}	
}
void Counterpoise_Heap(MinHeap H, int index, int i, int Weight)
{
	for(; Weight < H ->Data[i/2].Weight; i /= 2){
		H ->Data[i].Weight = H ->Data[i/2].Weight;
		H ->Data[i].V = H ->Data[i/2].V;
	}
	H ->Data[i].Weight = Weight;
	H ->Data[i].V = index;
	return ;
}
bool IsEmpty_Heap(MinHeap H)
{
	return (H ->Size == 0);
}
DistNode Pop_Heap(MinHeap H, bool *collected)
{
	DistNode Min, Temp;
	int Parent, Child;
	if(IsEmpty_Heap(H)){
		return H ->Data[0];
	}
	Min = H ->Data[1];
	Temp = H ->Data[H ->Size --];
	collected[Min.V] = false;
	for(Parent = 1; Parent *2 < H ->Size; Parent = Child){
		Child = Parent * 2;
		if(H ->Data[Child].Weight > H ->Data[Child + 1].Weight){
			Child++;
		}
		if(Temp.Weight <= H ->Data[Child].Weight){
			break;
		}else{
			H ->Data[Parent].Weight = H ->Data[Child].Weight;
			H ->Data[Parent].V = H ->Data[Child].V;
		}
	}
	H ->Data[Parent].Weight = Temp.Weight;
	H ->Data[Parent].V = Temp.V;
	return Min;
}

 第二个kruskal算法， 最小堆+并查树+Kruskal。

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
 
#define MaxVertex 1001
#define INFITY 100001
#define MinValue -1
 
typedef struct ENode Edge;
struct ENode{
	int V1, V2;
	int Weight;
};
 
typedef struct GNode *MGraph;
struct GNode{
	int Nv;
	int Ne;
	int G[MaxVertex][MaxVertex];
};
  
typedef struct Heap *MinHeap;
struct Heap{
	Edge *Data;
	int Size;
};

//便于并查树算法理解，有心吧。
typedef struct UnionFind *UF;
struct UnionFind{
	int Parent;
};
 
MGraph Build_Graph();
MGraph Init_Graph();
void Insert_Graph(MGraph M, Edge E);
MinHeap Init_Heap(int N);
MinHeap Creat_Heap(MGraph M);
void Push_Heap(MinHeap H, int V1, int V2, int Weight);
bool IsEmpty_Heap(MinHeap H);
Edge Pop_Heap(MinHeap H);
UF Init_UnionFind(int VertexNum);
void Union_Value(UF T, int V1, int V2);
int Find_Root(UF T, int V);
bool Check_Loop(UF T, int V1, int V2);
void Kruskal(MGraph M, MinHeap H, UF T, bool *Visited, int *dist);
 
int main()
{
	MGraph M;
	MinHeap H;
	UF T;
	int *dist;
	bool *Visited;
	M = Build_Graph();
	H = Creat_Heap(M);	
	T = Init_UnionFind(M ->Nv);
	dist = (int*)malloc(sizeof(int) * M ->Nv);
	Visited = (bool*)calloc(M ->Nv, sizeof(bool));
	Kruskal(M, H, T, Visited, dist);
	return 0;
}
void Kruskal(MGraph M, MinHeap H, UF T, bool *Visited, int *dist)
{
	Edge Data;
	int i = 1;
	int cost = 0;
	while(Data = Pop_Heap(H), (Data.Weight > 0 && i < M ->Nv)){
		if(!Check_Loop(T, Data.V1, Data.V2)){
			Union_Value(T, Data.V1, Data.V2);
			cost += Data.Weight;
			i++;
		}
	}
	if(i != M ->Nv){
		printf("-1\n");
	}else{
		printf("%d\n", cost);
	}
}

MGraph Build_Graph()
{
	MGraph M;
	Edge E;
	M = Init_Graph();
	for(int i = 0; i < M ->Ne; i++){
		scanf("%d %d %d", &E.V1, &E.V2, &E.Weight);
		E.V1 --; E.V2 --;
		Insert_Graph(M, E);
	}
	return M;
}
MGraph Init_Graph()
{
	MGraph M;
	M = (MGraph)malloc(sizeof(struct GNode));
	scanf("%d %d", &M ->Nv, &M ->Ne);
	for(int i = 0; i < (M ->Nv); i++){
		for(int j = 0; j < (M ->Nv); j++){
			M ->G[i][j] = INFITY;
		}
	}
	return M;
}
void Insert_Graph(MGraph M, Edge E)
{
	M ->G[E.V1][E.V2] = E.Weight;
	M ->G[E.V2][E.V1] = E.Weight;
}
 
MinHeap Creat_Heap(MGraph M)
{
	MinHeap H;
	H = Init_Heap(M ->Ne);
	for(int i = 0; i < M ->Nv; i++)
		for(int j = i + 1; j < M ->Nv; j++){
			if(M ->G[i][j] < INFITY){
				Push_Heap(H, i, j, M ->G[i][j]);
			}
		}
	return H;
}
MinHeap Init_Heap(int N)
{
	MinHeap H;
	H = (MinHeap)malloc(sizeof(struct Heap));
	H ->Data = (Edge*)malloc(sizeof(Edge) * (N + 1));
	H ->Data[0].Weight = MinValue;
	H ->Size = 0;
	return H;
}
void Push_Heap(MinHeap H, int V1, int V2, int Weight)
{
	int i;
	i = ++(H ->Size);
	for(; Weight < H ->Data[i/2].Weight; i /= 2){
		H ->Data[i].Weight = H ->Data[i/2].Weight;
		H ->Data[i].V1 = H ->Data[i/2].V1;
		H ->Data[i].V2 = H ->Data[i/2].V2;
	}
	H ->Data[i].Weight = Weight;
	H ->Data[i].V1 = V1;
	H ->Data[i].V2 = V2;
	return ;	
}

bool IsEmpty_Heap(MinHeap H)
{
	return (H ->Size == 0);
}
Edge Pop_Heap(MinHeap H)
{
	Edge Min, Temp;
	int Parent, Child;
	if(IsEmpty_Heap(H)){
		return H ->Data[0];
	}
	Min = H ->Data[1];
	Temp = H ->Data[H ->Size --];
	for(Parent = 1; Parent *2 < H ->Size; Parent = Child){
		Child = Parent * 2;
		if(H ->Data[Child].Weight > H ->Data[Child + 1].Weight){
			Child++;
		}
		if(Temp.Weight <= H ->Data[Child].Weight){
			break;
		}else{
			H ->Data[Parent].Weight = H ->Data[Child].Weight;
			H ->Data[Parent].V1 = H ->Data[Child].V1;
			H ->Data[Parent].V2 = H ->Data[Child].V2;
		}
	}
	H ->Data[Parent].Weight = Temp.Weight;
	H ->Data[Parent].V1 = Temp.V1;
	H ->Data[Parent].V2 = Temp.V2;
	return Min;
}
UF Init_UnionFind(int VertexNum)
{
	UF T;
	T = (UF)malloc(sizeof(struct UnionFind) * (VertexNum + 1));
	for(int i = 0; i < VertexNum; i++){
		T[i].Parent = -1;
	}
	return T;
}
void Union_Value(UF T, int V1, int V2)
{
	int Root1, Root2;
	Root1 = Find_Root(T, V1);
	Root2 = Find_Root(T, V2);
	if(T[Root1].Parent < T[Root2].Parent){
		T[Root1].Parent += T[Root2].Parent;
		T[Root2].Parent = Root1;
	}else{
		T[Root2].Parent += T[Root1].Parent;
		T[Root1].Parent = Root2;
	}
}
int Find_Root(UF T, int V)
{
	if(T[V].Parent < 0){
		return V;
	}
	return Find_Root(T, T[V].Parent);
}
bool Check_Loop(UF T, int V1, int V2)
{
	if(Find_Root(T, V1) == Find_Root(T, V2)){
		return true;
	}else{
		return false;
	}
}

2024.9.6-错误借鉴，哈哈，我竟然，好吧，就是没有好好听课，不是最短路，而是最小边，之前的样例我感觉只是运气吧。

测试点提示内存(KB)用时(ms)结果得分
0sample换数字，各种回路判断1844

答案正确

15 / 15
1M<N-1，不可能有生成树1884

答案正确

2 / 2
2M达到N-1，但是图不连通3164

答案正确

2 / 2
3最大N和M，连通41568

答案错误

0 / 5
4最大N和M，不连通41567

答案正确

6 / 6

void Prim(MGraph M, MinHeap H, bool* Visited, int *dist)
{
	int j;
	bool *collected;
	collected = (bool*)calloc(M ->Nv, sizeof(bool));
	for(j = 0; j < M ->Nv; j++){
		dist[j] = INFITY;
	}
	DistNode Data;
	Creat_Heap(M, H, 0, Visited, collected);
	Visited[0] = true;
	dist[0] = 0;
	while(Data = Pop_Heap(H, collected), Data.Weight > 0){
		if(!Visited[Data.V] && dist[Data.V] > Data.Weight){
			dist[Data.V] = Data.Weight;
		}
		Visited[Data.V] = true;
		for(j = 0; j < M ->Nv; j++){
			if(!Visited[j] && M ->G[Data.V][j] < INFITY && (dist[j] > dist[Data.V] + M ->G[Data.V][j])){
				dist[j] = M ->G[Data.V][j];
				Push_Heap(H, j, dist[j], collected);
				//有人会问，这样不会产生数据重复吗，注意Visited,遵循一次访问原则。
			}
		}
	}	
}


http://www.kler.cn/a/300916.html

相关文章：

  • hadoop3.3和hive4.0安装——单节点
  • WEB 攻防-通用漏-XSS 跨站脚本攻击-反射型/存储型/DOMBEEF-XSS
  • 迅为RK3568开发板篇OpenHarmony配置HDF驱动控制LED-新增 topeet子系统-编写 bundle.json文件
  • 【无标题】
  • WordPress如何配置AJAX以支持点击加载更多？
  • 单片机的原理及其应用：从入门到进阶的全方位指南
  • C#简单计算机项目（优化后版本）
  • JVM 调优篇3 jvm对象的内存布局与执行引擎
  • MongoDB入门教程
  • 如何通过可视化大屏，打通智慧城市建设的“最后一公里”？
  • 初识Linux · 有关gdb
  • 基于SpringBoot+Vue+MySQL的考研互助交流平台
  • 如何选择大带宽服务器租用
  • Mybatis中ORB映射
  • Servlet编程第一步：从零构建Hello World应用，详细步骤+图解
  • 本地部署Llama 3.1大模型
  • 价值流：从理论框架到实践落地的系统化指南
  • 快速解决git am冲突
  • 【从问题中去学习k8s】k8s中的常见面试题（夯实理论基础）（二十九）
  • 一维数组 list 呢 ，怎么转换成 (批次 句子长度 特征值 )三维向量 python pytorch lstm 编程 人工智能
  • OCR在线识别网站现已上线！
  • Nuxt Kit 的使用指南：从加载到构建
  • Windows下Python和PyCharm的应用(三)__Numpy与矩阵
  • 插入、希尔、冒泡、选择排序
  • EG边缘计算网关连接阿里云物联网平台（MQTT协议）
  • 22_图论中的高级数据结构