1879 继续畅通工程
题目详情：
继续畅通工程
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 38057 Accepted Submission(s): 15708
当N为0时输入结束。 Output 每个测试用例的输出占一行，输出全省畅通需要的最低成本。 Sample Input 3 1 2 1 0 1 3 2 0 2 3 4 0 3 1 2 1 0 1 3 2 0 2 3 4 1 3 1 2 1 0 1 3 2 1 2 3 4 1 0 Sample Output 3 1 0 Author ZJU Source 浙大计算机研究生复试上机考试-2008年 Recommend We have carefully selected several similar problems for you: 1875 1102 1856 1874 1301
题目大意：
有n个村庄,相互分隔，现在准备修路，使所有村庄相通（直接或间接相连），有的相通的村庄有路就不需要修，有的村庄没有路，则需要修路，求要使所有村庄相通，所修的路的最少花费。
解题思路：
在并查集的基础上融合了贪心，想要修的路花费最短，先把有路的村庄连接起来，则再把村庄间的修路的花费按照递增排序，再遍历判断两个村庄是否相连，最后输出最少花费。
AC代码：
#include
#include
using namespace std;
int num[101];
class village{public:int first_village;int last_village;int road_cost;int rosd_status;int find_boss(int a){int temporary=a;while(num[temporary]!=temporary){temporary=num[temporary];}return num[temporary];}void merge(int village_one,int village_two){if(find_boss(village_one)!=find_boss(village_two)){num[find_boss(village_one)]=find_boss(village_two);//合并}}
};
bool cmp(village village_one,village village_two){return village_one.road_cost>n&&n){village v[((n-1)*n)/2];int road_cost=0;//道路总长初始化int one=0;for(int i=0;i<101;++i){num[i]=i;//初始化}for(int i=0;i<((n-1)*n)/2;++i){cin>>v[i].first_village>>v[i].last_village>>v[i].road_cost>>v[i].rosd_status;//输入if(v[i].rosd_status==1) v[i].merge(v[i].first_village,v[i].last_village);}sort(v,v+((n-1)*n)/2,cmp);for(int i=0;i<((n-1)*n)/2;++i){if(v[i].find_boss(v[i].first_village)!=v[i].find_boss(v[i].last_village)){//如果没有相连则相连起来v[i].merge(v[i].first_village,v[i].last_village); road_cost+=v[i].road_cost;}}cout< 一开始用cin效率太低导致超时,消除缓存和绑定后AC了。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！