本文主要是介绍洛谷 1111.修复公路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：并查集
这里需要用到结构体，本来开始的时候作者还为怎么存储那么多数据而烦恼，反倒是忘记了有结构体这种解法了。
并查集其实并不是实际意义上的无向图，这一点大家需要铭记，我们在找共同根的时候还是需要全部结点都遍历一下去判断一下根的，而不是随便选择一个数就行了。作者在这里就犯蠢了，把并查集认为是无向图了。
其他的地方，就是对于结构体数组进行排序的时候是按照时间的从短到长进行排序的。
上代码：
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<deque>
#include <iomanip>
#include<sstream>
#include<numeric>
#include<map>
#include<limits.h>
#include<unordered_map>
#include<set>
#define int long long
#define MAX 100010
#define inf 0x3f3f3f3f
#define _for(i,a,b) for(int i=a;i<(b);i++)
using namespace std;
typedef pair<int, int> PII;
int n,m;
int counts,u=1;
int dx[] = { 0,1,0,-1};
int dy[] = { 1,0,-1,0 };
int f[MAX];
struct node {int x;int y;int t;
}pace[MAX];
int find(int x) {if (f[x] == x)return x;elsereturn f[x] = find(f[x]);
}
void unit(int x, int y) {int s = find(x);f[s] = find(y);
}
bool cmp(node a, node b) {return a.t < b.t;
}
signed main() {ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);cin >> n >> m;for (int i = 1; i <= n; i++) {f[i] = i;}for (int i = 1; i <= m; i++) {cin >> pace[i].x >> pace[i].y >> pace[i].t;}bool flag=true;sort(pace + 1, pace + m + 1, cmp);for (int i = 1; i <= m; i++) {flag = true;unit(pace[i].x, pace[i].y);int gong;for (int k = 1; k <= n; k++) {if (f[k] == k)gong = k;}for (int j = 1; j <= n; j++) {if (find(j) != gong)flag = false;}if (flag) {cout << pace[i].t << endl;return 0;}}cout << -1 << endl;return 0;
}这篇关于洛谷 1111.修复公路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
