(最小生成树 并查集)P1111 修复公路 洛谷

题目背景

A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

题目描述

给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）

输入输出格式

输入格式：

 

第1行两个正整数N,M

下面MM行，每行3个正整数x,y,t，告诉你这条公路连着x,y两个村庄，在时间t时能修复完成这条公路。

 

输出格式：

 

如果全部公路修复完毕仍然存在两个村庄无法通车，则输出−1，否则输出最早什么时候任意两个村庄能够通车。

 

输入输出样例

输入样例#1：  复制 4 4 1 2 6 1 3 4 1 4 5 4 2 3 输出样例#1：  复制 5

说明

N≤1000,M≤100000

x≤N,y≤N,t≤100000

------------------------------------------------------------------------------------------------------------------------------------------------------------------

emmmm，Kruskal模板题，用并查集优化

C++代码：

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int N = 1003; struct Edge{ int x; int y; int t; }e[100003]; bool cmp(Edge a,Edge b){ return a.t < b.t; } int n,m; int father[N]; void Init(int n){ for(int i = 1; i <= n; i++) father[i] = i; } int Find(int x){ if(x != father[x]){ father[x] = Find(father[x]); } return father[x]; } int Merge(int x,int y){ int p = Find(x); int q = Find(y); if(p == q) return 0; if(p > q) father[p] = q; else father[q] = p; } int Kruskal(int n,int m){ int ans = 0; for(int i = 1; i <= m; i++){ if(Merge(e[i].x,e[i].y)){ ans = e[i].t; n--; if(n == 1) return ans; } } return -1; } int main(){ cin>>n>>m; Init(n); for(int i = 1; i <= m; i++){ cin>>e[i].x>>e[i].y>>e[i].t; } sort(e+1,e+m+1,cmp); int ans = Kruskal(n,m); cout<<ans<<endl; return 0; }

 

转载于:https://www.cnblogs.com/Weixu-Liu/p/10651745.html

相关资源：Uyghurapp Y（安卓维文字体安装器）