题目背景

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

题目描述

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

输入格式

第11行两个正整数N,MN,M

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

输出格式

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

输入输出样例

输入 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
4 4
1 2 6
1 3 4
1 4 5
4 2 3
输出 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
5

 

 

CODE

 

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 template<class T>inline void read(T &res)
 10 {
 11     char c;T flag=1;
 12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 14 }
 15 
 16 namespace _buff {
 17     const size_t BUFF = 1 << 19;
 18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
 19     char getc() {
 20         if (ib == ie) {
 21             ib = ibuf;
 22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
 23         }
 24         return ib == ie ? -1 : *ib++;
 25     }
 26 }
 27 
 28 int qread() {
 29     using namespace _buff;
 30     int ret = 0;
 31     bool pos = true;
 32     char c = getc();
 33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
 34         assert(~c);
 35     }
 36     if (c == '-') {
 37         pos = false;
 38         c = getc();
 39     }
 40     for (; c >= '0' && c <= '9'; c = getc()) {
 41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
 42     }
 43     return pos ? ret : -ret;
 44 }
 45 
 46 const int maxn = 1e3 + 7;
 47 
 48 int fa[maxn];
 49 int n,m;
 50 
 51 struct node {
 52     int x, y, time;
 53 }a[100007];
 54 
 55 bool cmp(node a, node b) {
 56     return a.time < b.time;
 57 }
 58 
 59 int fid(int x) {
 60     return x == fa[x] ? x : fid(fa[x]);
 61 }
 62 
 63 void join(int x, int y) {
 64     int r1 = fid(x), r2 = fid(y);
 65     if(r1 != r2) {
 66         fa[r2] = r1;
 67         //printf("fa[%d]:%d\n",r2,fa[r2]);
 68     }
 69 }
 70 
 71 int main()
 72 {
 73     int maxx = 0;
 74     scanf("%d %d", &n, &m);
 75     for ( int i = 1; i <= m; ++i ) {
 76         scanf("%d %d %d",&a[i].x, &a[i].y, &a[i].time);
 77         maxx = max(maxx, a[i].time);
 78     }
 79     sort(a + 1, a + m + 1, cmp);
 80     for ( int i = 1; i <= n; ++i ) {
 81         fa[i] = i;
 82     }
 83     int id = 1;
 84     for ( int i = 0; i <= maxx; ++i ) {
 85         for ( int j = id; j <= m; ++j ) {
 86             //printf("i:%d a[%d].time:%d\n",i,j,a[j].time);
 87             if(i >= a[j].time) {
 88                 id = j;
 89                 join(a[j].x, a[j].y);
 90             }
 91             else
 92                 break;
 93         }
 94         int cnt = 0;
 95         for ( int j = 1; j <= n; ++j ) {
 96             if(fa[j] == j)
 97                 cnt++;
 98             if(cnt >= 2)
 99                 break;
100         }
101         if(cnt == 1) {
102             cout << i << endl;
103             return 0;
104         }
105     }
106     cout << -1 << endl;
107     return 0;
108 }
View Code