题2 修复公路(road)
【问题描述】
A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
【数据输入】
第1行两个正整数N，M（N<=1000，M<=）
下面M行，每行3个正整数x, y, t，告诉你这条公路连着x,y两个村庄，在时间t时能修复完成这条公路。（x<=N，y<=N，t<=）
【数据输出】
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1，否则输出最早什么时候任意两个村庄能够通车。
【样例输入】
4 4
1 2 6
1 3 4
1 4 5
4 2 3
【样例输出】
5
一、使用堆对边排序
#include
#include
using namespace std; const int N = 1010,M = ; typedef pair
> PIP; priority_queue
,greater
> que; int f[N],count,sum = -1; //获得v的祖宗 int get_f(int v){ if(f[v] == v){ return v; }else{ f[v] = get_f(f[v]); return f[v]; } } //两个点合成同个集合 bool merge(int v,int u){ int t1 = get_f(v); int t2 = get_f(u); //若祖宗不同，即不是同个集合，就进行合并 if(t1 != t2){ f[t2] = t1;//靠左原则：t1为祖宗 return true; } return false; } int main(){ // freopen("road.in","r",stdin); // freopen("road.out","w",stdout); int n,m; cin>>n>>m; for(int i = 1; i <= n; i++) f[i] = i; for(int i = 1; i <= m; i++){ int x,y,t; cin>>x>>y>>t; que.push(make_pair(t,make_pair(x,y))); } //Kruskal生成树 for(int i = 1; i <= m; i++){ pair
top = que.top().second; int t = que.top().first; que.pop(); if(merge(top.first,top.second)){ count++; sum = max(sum,t); } if(count == n-1) break; } //若生成的边数小于n-1说明有孤立的村庄 if(count < n-1){ cout<<-1; return 0; } cout<
二、使用内置排序函数sort
#include
#include
#include
using namespace std; const int N = 1010,M = ; typedef pair
> PIP; PIP k[M]; //priority_queue
,greater
> que; int f[N],ct,sum = -1; //获得v的祖宗 int get_f(int v){ if(f[v] == v){ return v; }else{ f[v] = get_f(f[v]); return f[v]; } } //两个点合成同个集合 bool merge(int v,int u){ int t1 = get_f(v); int t2 = get_f(u); //若祖宗不同，即不是同个集合，就进行合并 if(t1 != t2){ f[t2] = t1;//靠左原则：t1为祖宗 return true; } return false; } int main(){ // freopen("road.in","r",stdin); // freopen("road.out","w",stdout); int n,m; cin>>n>>m; for(int i = 1; i <= n; i++) f[i] = i; for(int i = 1; i <= m; i++){ cin>>k[i].second.first>>k[i].second.second>>k[i].first; } sort(k+1,k+m+1); for(int i = 1; i <= m; i++){ int u = k[i].second.first; int v = k[i].second.second; int t = k[i].first; if(merge(u,v)){ ct++; sum = max(sum,t); } if(ct == n-1) break; } if(ct != n-1){ cout<<-1; return 0; } cout<
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/216374.html原文链接：https://javaforall.net
