2377:Bad Cowtractors

keyword

MST　C++

概要

辺と重みが与えられたとき最大重み全域木を求める問題。
符号を逆にして最小重み全域木に帰着させるとかわざわざしなくても重みの大きい辺から貪欲に付け足していけば良い。むしろこっちの方がpriority_queueのデフォルトがそのまま使えるのでコード量的に楽。

int ps[1001];

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

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

void merge(int x, int y){
    int xx = getRoot(x), yy = getRoot(y);
    ps[xx] = yy;
    return ;
}

int main(){
    priority_queue< pair<int, pair<int, int> > > Q;
    int i, n, m, x, y, c, cnt = 0,total=0;
    scanf("%d%d",&n,&m);
    REPONE(i,n) ps[i] = i;
    REP(i,m){
        scanf("%d%d%d",&x,&y,&c);
        Q.push(MP(c,MP(x,y)));
    }

    while(!Q.empty() && cnt < n-1){
        pair<int, pair<int, int> > t = Q.top();
        if(!isSame(t.sc.fs, t.sc.sc)){
            total += t.fs;
            cnt++;
            merge(t.sc.fs, t.sc.sc);
        }
        Q.pop();
    }

    printf("%d\n", (cnt<n-1)?-1:total);
    return 0;
}