并查集--同时修路得到的最短时间

题目背景

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

题目描述

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1复制

4 4 1 2 6 1 3 4 1 4 5 4 2 3

输出 #1复制

说明/提示

N \le 1000,M \le 100000N≤1000,M≤100000

x \le N,y \le N,t \le 100000x≤N,y≤N,t≤100000

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

int father[1005];
int N, M;

struct Node {
int x, y;
int value;
}n[100005];

bool Cmp(const Node& a, const Node& b) {
return a.value < b.value;
}

int find(int x) {
if (x != father[x]) {
return father[x] = find(father[x]);
  }
return father[x] = x;
}

bool Judge() {
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
if (find(i) != find(j)) {
return false;
      }
    }
  }
return true;
}

int main() {
scanf("%d%d", &N, &M);
for (int i = 1; i <= M; i++) {
scanf("%d%d%d", &n[i].x, &n[i].y, &n[i].value);
  }
sort(n + 1, n + M + 1,Cmp);
for (int i = 1; i <= N; i++) {
father[i] = i;
  }
for (int i = 1; i <= M; i++) {
int a = find(n[i].x);
int b = find(n[i].y);
if (a != b) {
father[a] = b;
if (Judge()) {
printf("%d\n", n[i].value);
return 0;
      }
    }
  }
printf("-1\n");
return 0;
}

秒客网