08-图7 公路村村通 (30分)(C语言实现)(数据结构)

本文主要是介绍08-图7 公路村村通 (30分)(C语言实现)(数据结构)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

输入样例:

输出样例:

我们首先需要定义结构体以及其他一些定义

#include<stdio.h>
#define Max 1000
typedef struct
{int x,y;int cost;
}city;
typedef struct//堆
{city data[3005];int size;
}Minheap;
Minheap minh;
int n,m;
int path[1005];//用来存放父结点的下标(集合操作),每个数组下标存放父亲结点，为根节点则为0

函数的声明

void Kruskal();
city del(Minheap &h);

首先看一下堆的操作

void init(Minheap &h)//初始化堆
{h.size=0;h.data[0].cost=-1;
}
void insert(Minheap &h,city a)//堆的插入操作
{int i=++h.size;//传入一个容量+1for(;i>0&&a.cost<h.data[i/2].cost;i/=2){h.data[i]=h.data[i/2];}h.data[i]=a;
}
city del(Minheap &h)//最小堆中的删除操作
{city min=h.data[1];/*我们是从数组下标为1开始存入数据的，所以此时为最小值*/city last=h.data[h.size--];if(h.size==0) return min;int i=2;for(;i<=h.size;){if(h.data[i].cost>h.data[i+1].cost&&i<h.size)/*在堆中，父结点值肯定比子树要小，但是左右子树就不确定了*/i++;if(h.data[i].cost<last.cost) //从子树找更小的值代替根节点，再从子树的子树找更小的代替子树{h.data[i/2]=h.data[i];i*=2;}else break;}h.data[i/2]=last;return min;
}

判断是否属于一个集合

int judgeroot(city a){while(path[a.x]!=0) {a.x=path[a.x];}         //进行循环,直到找到根while(path[a.y]!=0) {a.y=path[a.y];}if(a.x==a.y) return 0;else {path[a.x]=a.y;return 1;}
}

核心算法

void Kruskal()//算法
{int v=0,mincost=0;while(v!=n-1&&minh.size!=0)//有公路数{city a=del(minh);if(judgeroot(a))//判断是否属于同一个集合,如果属于同一个集合，错误{v++;//连通数加1mincost+=a.cost;//加上这条道路的花费}}	if(v!=n-1)  printf("-1\n");//没有连通,中途操作没有执行完else printf("%d\n",mincost);//打印最小花费
}

主函数

int main(){city a;init(minh);scanf("%d%d",&n,&m);//输入城镇数目和候选道路数for(int i=0;i<m;i++){scanf("%d%d%d",&a.x,&a.y,&a.cost);//输入道路号和代价insert(minh,a);//插入堆中}Kruskal(); //算法
}

文章总代码如下

#include<stdio.h>
#define Max 1000
typedef struct
{int x,y;int cost;
}city;
typedef struct//堆
{city data[3005];int size;
}Minheap;
Minheap minh;
int n,m;
int path[1005];//用来存放父结点的下标(集合操作)void Kruskal();
city del(Minheap &h);void init(Minheap &h)//初始化堆
{h.size=0;h.data[0].cost=-1;
}
void insert(Minheap &h,city a)//堆的插入操作
{int i=++h.size;//传入一个容量+1for(;i>0&&a.cost<h.data[i/2].cost;i/=2){h.data[i]=h.data[i/2];}h.data[i]=a;
}
int judgeroot(city a){while(path[a.x]!=0) {a.x=path[a.x];}         //进行循环,直到找到根while(path[a.y]!=0) {a.y=path[a.y];}if(a.x==a.y) return 0;else {path[a.x]=a.y;return 1;}
}
void Kruskal()//算法
{int v=0,mincost=0;while(v!=n-1&&minh.size!=0)//有公路数{city a=del(minh);if(judgeroot(a))//判断是否属于同一个集合,如果属于同一个集合，错误{v++;//连通数加1mincost+=a.cost;//加上这条道路的花费}}	if(v!=n-1)  printf("-1\n");//没有连通,中途操作没有执行完else printf("%d\n",mincost);//打印最小花费
}
city del(Minheap &h)//最小堆中的删除操作
{city min=h.data[1];/*我们是从数组下标为1开始存入数据的，所以此时为最小值*/city last=h.data[h.size--];if(h.size==0) return min;int i=2;for(;i<=h.size;){if(h.data[i].cost>h.data[i+1].cost&&i<h.size)/*在堆中，父结点值肯定比子树要小，但是左右子树就不确定了*/i++;if(h.data[i].cost<last.cost) //从子树找更小的值代替根节点，再从子树的子树找更小的代替子树{h.data[i/2]=h.data[i];i*=2;}else break;}h.data[i/2]=last;return min;
}int main(){city a;init(minh);scanf("%d%d",&n,&m);//输入城镇数目和候选道路数for(int i=0;i<m;i++){scanf("%d%d%d",&a.x,&a.y,&a.cost);//输入道路号和代价insert(minh,a);//插入堆中}Kruskal(); //算法
}