2485 Highways

2485 Highways

n個の町を高速道路で繋ぐ計画。

どの町にも高速を使ってアクセスできるようにするとき、町間の高速道路の長さの最大値が

最小になるような計画を立てて、最大値を答える問題。

最少全域木問題だから、貪欲法で解ける。
初めてunion findを使ったから記念に。

DisjointSetクラスのメソッドたち

・void makeSet(int x) xだけからなる集合を作る

・void myunion(int x, int y) xとyを合併する

・int findSet(int x) xが含まれる集合の代表を求める

・bool isSameSet(int x, int y) xとyが同じ集合に含まれればtrue

注意点としてはmakeSet(x)する前にfindSet(x)!=0でxを含む集合が存在しないことを確認すること。
あと、このDisjointSetだとmakeSet(0)ができないので注意。（0で集合が存在しないことを示しているため）

#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

// 町i-j間の距離はd
struct Dist {
    int d, i, j;
    Dist(int d, int i, int j) :
        d(d), i(i), j(j) {}
    bool operator < (const Dist &dist) const {
        return d > dist.d;
    }
};

// union find用
class DisjointSet{
    public:
    DisjointSet(){}
    DisjointSet( int size ){
        rank.resize( size, 0 );
        p.resize( size, 0 );
    }
    
    void makeSet( int x ){
        p[x] = x;
        rank[x] = 0;
    }
    
    void myunion( int x, int y ){
        link( findSet(x), findSet(y) );
    }
    
    int findSet( int x ){
        if ( x != p[x] ) p[x] = findSet( p[x] );
        return p[x];
    }
    
    bool isSameSet( int x, int y ){
        return ( findSet(x) == findSet(y) );
    }
    
    private:
    vector<int> rank, p;
    
    void link ( int x, int y ){
        if ( rank[x] > rank[y] ){
            p[y] = x;
        } else {
            p[x] = y;
            if ( rank[x] == rank[y] ) rank[y]++;
        }
    }
};

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        priority_queue<Dist> Q;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                int d;
                scanf("%d", &d);
                if (j > i) Q.push(Dist(d, i, j));
            }
        }
        DisjointSet DS = DisjointSet(n+1);
        int ret = 0;

        for (int cnt = 0; cnt < n-1; ) { // 道をn-1本作ったら全域木になる
            Dist dist = Q.top(); Q.pop();
            if (!DS.findSet(dist.i)) DS.makeSet(dist.i);
            if (!DS.findSet(dist.j)) DS.makeSet(dist.j);
            if (DS.isSameSet(dist.i, dist.j)) continue;
            DS.myunion(dist.i, dist.j);
            ret = dist.d;
            ++cnt;
        }
        printf("%d\n", ret);
    }
}