华师一附中OI组

标题: P1111 修复公路 [打印本页]

---

作者: 倚窗倾听风吹雨    时间: 2018-10-4 16:54
标题: P1111 修复公路
https://www.luogu.org/problemnew/show/P1111


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

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

输入输出格式
输入格式：
第1行两个正整数N,M
下面M行，每行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

---

作者: 倚窗倾听风吹雨    时间: 2018-10-4 16:54


并查集裸题

1. #include<iostream>
   
2. #include<algorithm>
   
3. #define FOR(i,a,b) for(register int i=a;i<=b;i++)
   
4. using namespace std;
   
5. const int N=1005,M=100005;
   
6. int n,m,a[N];
   
7. struct node
   
8. {
   
9.     int b,e,t;
   
10.     bool operator < (node x){return t<x.t;}
    
11. }ch[M];
    
12. int getf(int q)
    
13. {
    
14.     if(a[q]==q)return q;
    
15.     a[q]=getf(a[q]);
    
16.     return a[q];
    
17. }
    
18. int main()
    
19. {
    
20.     cin>>n>>m;
    
21.     FOR(i,1,m)
    
22.     cin>>ch[i].b>>ch[i].e>>ch[i].t;
    
23.     sort(ch+1,ch+m+1);///FOR(i,1,m)cout<<ch[i].b<<" "<<ch[i].e<<" "<<ch[i].t<<endl;
    
24.     FOR(i,1,n)a[i]=i;
    
25.     FOR(i,1,m)
    
26.     {
    
27.         int t1=getf(ch[i].b),t2=getf(ch[i].e);
    
28.         if(t1!=t2){a[t2]=t1;n--;}
    
29.         if(n==1){cout<<ch[i].t<<endl;return 0;}
    
30.     }
    
31.     cout<<-1<<endl;
    
32.     return 0;
    
33. }
    
34. /*
    
35. 4 4
    
36. 1 2 6
    
37. 1 3 4
    
38. 1 4 5
    
39. 4 2 3
    
40. */

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2