Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- bool isDiag = false;
- int n, m;
- struct Edge{
- int d, w;
- Edge(){};
- Edge(int d, int w): d(d), w(w) {}
- };
- int loc[100001];
- int component[100001];
- vector<Edge> edges[100001];
- void dfs(int curr, int label, int minW){
- if(component[curr] == label){
- return;
- }
- if(isDiag) cout << "[dfs] curr: " << curr << ", label: " << label << ", minW: " << minW << endl;
- component[curr] = label;
- for (Edge child: edges[curr])
- {
- if (child.w >= minW)
- {
- dfs(child.d, label, minW);
- }
- }
- }
- bool valid(int minW){
- memset(component, -1, sizeof(component));
- int label = 0;
- for (int i = 1; i <= n; i++)
- {
- if (component[i] < 0)
- {
- dfs(i, label++, minW);
- }
- }
- for (int i = 1; i <= n; i++)
- {
- if (component[i] != component[loc[i]])
- {
- if(isDiag) cout << "!!Invalid for component[" << i << "] label=" << component[i]
- << " vs. [" << loc[i] << "] label=" << component[loc[i]] << endl;
- return false;
- }
- }
- return true;
- }
- int main(){
- //isDiag = true;
- freopen( "wormsort.in", "r", stdin);
- cin >> n >> m;
- if(isDiag) cout << "n: " << n << ", m: " << m << endl;
- for (int i = 1; i <= n; i++)
- {
- cin >> loc[i];
- }
- for (int i = 0; i < m; i++)
- {
- int a, b, w;
- cin >> a >> b >> w;
- edges[a].push_back(Edge(b, w));
- edges[b].push_back(Edge(a, w));
- }
- int minW = 0, maxW = 1000000001;
- while (minW != maxW)
- {
- int mid = (minW + maxW + 1) /2 ;
- if(valid(mid)){
- minW = mid;
- if(isDiag) cout << "===Ok mid: " << mid << "====="<< endl;
- }else{
- maxW = mid - 1;
- }
- }
- if (minW > 1e9)
- {
- minW = -1;
- }
- if(!isDiag) freopen("wormsort.out", "w", stdout);
- cout << minW << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
