2421:Constructing Roads

keyword

最小全域木　C++

概要

頂点数N(<100)のグラフと距離行列が与えられる。辺を付け加えてグラフが連結になるようにしたい。追加する辺のコストの最小値を求める問題。
木ではないけど最小全域木と同じ様なアルゴリズムで求められる。この辺はgreedyにいけるのでいろんなやり方があると思う。

int ps[102];

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

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

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

int main(){
    int n, i, j, k, d, m, ans = 0, pos = 0;
    int dist[102][102];
    edge es[10002];
    scanf("%d",&n);
    REPONE(i,n) ps[i] = i;

    REP(i,n)REP(j,n){
        scanf("%d",&d);
        if(i!=j)es[pos++] = MP(d,MP(i+1,j+1));
    }
    sort(es,es+pos);

    scanf("%d",&m);
    REP(k,m){
        scanf("%d%d",&i,&j);
        merge(i,j);
    }

    REP(i,pos)if(!isSame(es[i].sc.fs,es[i].sc.sc)){
        merge(es[i].sc.fs,es[i].sc.sc);
        ans += es[i].fs;
    }

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

    return 0;
}