2485:Highways

keyword

最小全域木　C++

概要

N(<200)都市間の距離が与えられる。全域木で最大の長さを最小にしたとき、その最大の長さを求める問題。
最大値の最小化は2分探索が定石らしいけど、この問題は実はMSTを作って最大の長さを答えれば良い。最小全域木はほとんどgreedyにやって大丈夫っぽい。

int pars[501];
int g[501][501];

int getRoot(int x){
    if(x==pars[x]) return x;
    return pars[x] = getRoot(pars[x]);
}

bool isSame(int x, int y){
    return  getRoot(x) == getRoot(y);
}

void merge(int x, int y){
    pars[getRoot(x)] = getRoot(y);
}

int main(){
    int i, j, t, n;
    scanf("%d",&t);

    while(t--){
        scanf("%d",&n);
        REP(i,n) pars[i] = i;
        REP(i,n)REP(j,n) scanf("%d", *(g+i)+j);

        priority_queue<edge, vector<edge>, greater<edge> > Q;
        REP(i,n)for(j=i+1;j<n;j++){
            Q.push(MP(g[i][j],MP(i,j)));
        }

        int ans = 0, cnt = 0;
        while(cnt<n-1 && !Q.empty()){
            edge p = Q.top(); Q.pop();
            if(!isSame(p.sc.fs, p.sc.sc)){
                cnt++;
                ans = p.fs;
                merge(p.sc.fs, p.sc.sc);
            }
        }

        printf("%d\n",ans);
    }

    return 0;
}