08-图7 公路村村通 (30分)

是关于最小生成树的问题(包含v个顶点v-1条边，且边的权重和最小)，利用Kruskal贪心算法–将边合并成树，每次都取权值最小的边并且不构成回路，就利用到了并查集的算法（用数组存父节点）。

08-图7 公路村村通 (30分)

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

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

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

#include<stdio.h>
#define Max 1000
typedef struct{int x,y;int cost;
}box;
typedef struct{box data[3005];int size;
}heap;
heap minh;
int n,m;
int path[1005];
void init(heap &h){h.size=0;h.data[0].cost=-1; 
}
void insert(heap &h,box a){int i=++h.size;for(;i>0&&a.cost<h.data[i/2].cost;i/=2){h.data[i]=h.data[i/2];}h.data[i]=a;  
}
bool judgeroot(box 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 false;else {path[a.x]=a.y;return true;}
}
box del(heap &h){box min=h.data[1];box 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;
}
void swap(int& a,int &b){int temp=a;a=b;b=temp;
}
void Kruskal(){int v=0,mincost=0;while(v!=n-1&&minh.size!=0){box a=del(minh);//	for(int i=1;i<3;i++)printf("%d %d %d\n",minh.data[i].cost,minh.data[i].x,minh.data[i].y);if(judgeroot(a)){v++;mincost+=a.cost;}}	if(v!=n-1)  printf("-1\n");else printf("%d\n",mincost);
}
int main(){box a;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);}
//	for(int i=1;i<=m;i++) printf("%d %d %d\n",minh.data[i].cost,minh.data[i].x,minh.data[i].y);Kruskal();
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！