# 洛谷P1111 修复公路

## 题目背景

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

## 输入输出样例

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

5

## 说明

N<=1000，M<=100000

x<=N，y<=N，t<=100000

#include<iostream>
#include<algorithm>
using namespace std;
int vis[1007];
int father[1007];
int n, m;
struct node {
int start;
int end;
int time;

};
int  cmp(node a, node b) {
return a.time < b.time;
}
int find(int a) {
int x = a;
while(father[x] != x) {
x = father[x];
}
int y = a;
int z;
while(father[y] != y) {
z = y;
y = father[y];
father[z] = x;

}

return x;

}
int ac() {
int tot = 0;
for (int i = 1; i <= n; ++i) {
if(father[i] == i)
tot++;
}
}

void unionx(int a, int b) {
int fa = find(a);
int fb = find(b);
father[fb] = fa;
}

int main() {

cin >> n >> m;
node a[100007];
for (int i = 0; i < 1007; ++i) {
father[i] = i;
}
for (int i = 0; i < m; ++i) {
cin >> a[i].start >> a[i].end >> a[i].time;
}
int complish = 0;

sort(a, a + m, cmp);
int flag = -1;
for (int i = 0; i < m; ++i) {

unionx(a[i].start, a[i].end);

if(vis[a[i].start] == 0) {
complish++;
vis[a[i].start] = 1;
}
if(vis[a[i].end] == 0) {
complish++;
vis[a[i].end] = 1;
}
if(complish >= n && flag == -1 && ac() == 1) {
flag = a[i].time;
}

}

cout << flag << endl;

}

• ERROR:

2017年12月22日 下午11:13

抱大腿…以后有问题请教你！可以留个QQ吗？