1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <queue>

class UnionFind {
public:
    explicit UnionFind(int n) {
        parent_.resize(n);
        rank_.resize(n, 0);
        std::iota(parent_.begin(), parent_.end(), 0);
        count_ = n;
    }
    
    int Find(int x) {
        if (parent_[x] != x) {
            parent_[x] = Find(parent_[x]);
        }
        return parent_[x];
    }
    
    bool Union(int x, int y) {
        int root_x = Find(x);
        int root_y = Find(y);
        if (root_x == root_y) {
            return false;
        }
        
        if (rank_[root_x] < rank_[root_y]) {
            parent_[root_x] = root_y;
        }
        else if (rank_[root_x] > rank_[root_y]) {
            parent_[root_y] = root_x;
        }
        else {
            parent_[root_y] = root_x;
            ++rank_[root_x];
        }
        
        --count_;
        return true;
    }
    
    int getCount() const {
        return count_;
    }

private:
    std::vector<int> parent_;
    std::vector<int> rank_;
    int count_;
};

bool comp(std::vector<int>& A, std::vector<int>& B) {
    return A[3] > B[3] || (A[3] == B[3] && A[2] > B[2]);
}

class Solution {    
public:
    int maxStability(int n, std::vector<std::vector<int>>& edges, int k) {
        std::sort(edges.begin(), edges.end(), comp);
        UnionFind uf(n);
        
        int MinMust = 0x3fff'ffff;
        std::priority_queue<int> pq, pq2;
        
        for (auto& e : edges) {
            if (uf.Union(e[0], e[1])) {
                if (e[3] == 1) {
                    MinMust = std::min(MinMust, e[2]);
                }
                else {
                    pq.push(-e[2]);
                    if (uf.getCount() == 1) {
                        break;
                    }
                }
            }
            else if (e[3] == 1) {
                return -1;
            }
        }
        
        if (uf.getCount() != 1) {
            return -1;
        }
        if (pq.empty()) {
            return MinMust;
        }
        
        for (int i = 0; i < k && !pq.empty(); ++i) {
            int s = pq.top() * 2;
            pq.pop();
            pq2.push(s);
        }
        
        int MinOther = 0x3fff'ffff;
        if (!pq.empty()) {
            MinOther = std::min(-pq.top(), MinOther);
        }
        if (!pq2.empty()) {
            MinOther = std::min(-pq2.top(), MinOther);
        }
        
        return std::min(MinOther, MinMust);
    }
};