列表

详情

NC222472. [USACOJan2020S]WormholeSort

描述

Farmer John's cows have grown tired of his daily request that they sort themselves before leaving the barn each morning. They have just completed their PhDs in quantum physics, and are ready to speed things up a bit.
This morning, as usual, Farmer John's N cows (1≤N≤105), conveniently numbered 1…N, are scattered throughout the barn at N distinct locations, also numbered 1…N, such that cow i is at location pi. But this morning there are also M wormholes (1≤M≤105), numbered 1…M, where wormhole i bidirectionally connects location ai with location bi, and has a width wi (1≤ai,bi≤N,ai≠bi,1≤wi≤109).

At any point in time, two cows located at opposite ends of a wormhole may choose to simultaneously swap places through the wormhole. The cows must perform such swaps until cow i is at location i for 1≤i≤N.

The cows are not eager to get squished by the wormholes. Help them maximize the width of the least wide wormhole which they must use to sort themselves. It is guaranteed that it is possible for the cows to sort themselves.

输入描述

The first line contains two integers, N and M.
The second line contains the N integers p1,p2,…,pN. It is guaranteed that p is a permutation of 1…N.

For each i between 1 and M, line i+2 contains the integers ai, bi, and wi.

输出描述

A single integer: the maximum minimal wormhole width which a cow must squish itself into during the sorting process. If the cows do not need any wormholes to sort themselves, output −1.

示例1

输入: 

4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3

输出: 

9

说明:

Here is one possible way to sort the cows using only wormholes of width at least 9:

Cow 1 and cow 2 swap positions using the third wormhole.
Cow 1 and cow 3 swap positions using the first wormhole.
Cow 2 and cow 3 swap positions using the third wormhole.

示例2

输入: 

4 1
1 2 3 4
4 2 13

输出: 

-1

说明:

No wormholes are needed to sort the cows.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 702ms, 内存消耗: 7680K, 提交时间: 2023-06-05 08:47:41 

#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 10;
int n, m, a[maxN], fa[maxN];
vector<pair<int, int> > v[maxN];
set<int> s;
struct Node{int x, y, w;} e[maxN];
int find(int x){
    int r = x;
    while(r != fa[r]) r = fa[r];
    while(r != x){int p = fa[x]; fa[x] = r; x = p;}
    return r;
}
bool check(int x){
    for(int i = 1; i <= n; i++) fa[i] = i, v[i].clear();
    for(int i = 1; i <= m ; i++){
        if(e[i].w < x) continue;
        int fx = find(e[i].x), fy = find(e[i].y);
        if(fx != fy) fa[fx] = fy;
    }
    for(int i = 1; i <= n; i++){
        int fx = find(i);
        v[fx].push_back(make_pair(i, a[i]));
    }
    s.clear();
    set<int> :: iterator it;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < v[i].size(); j++){
            it = s.find(v[i][j].first);
            if(it != s.end()) s.erase(it);
            else s.insert(v[i][j].first);
            it = s.find(v[i][j].second);
            if(it != s.end()) s.erase(it);
            else s.insert(v[i][j].second);
        }
           
        if(s.size()) return 0;
    }
    return 1;
}
int bfind(int l, int r){
    int ans = -1;
    while(l <= r){
        int mid = l + r >> 1;
        if(check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    int flag = 1;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        flag &= i == a[i];
    }
    if(flag){cout << -1; return 0;}
    for(int i = 1; i <= m; i++) cin >> e[i].x >> e[i].y >> e[i].w;
    cout << bfind(1, 1e9);
    return 0;
}

上一题

© 2024 nowcoder.com