1287:Networking

keyword

最小全域木　C++

概要

MSTを求める問題。
書くだけ。

typedef pair<int, pair<int, int> > edge;

int par[52];

int getRoot(int x){
    if(x==par[x]) return x;
    return par[x] = getRoot(par[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);
    par[xx] = yy;
    return ;
}

int main(){
    int i, n, m, x, y, c, cnt, ans;

    while(scanf("%d",&n)){
        if(!n) break;
        scanf("%d",&m);
        priority_queue<edge, vector<edge>, greater<edge> > Q;
        REP(i,m){
            scanf("%d%d%d",&x,&y,&c);
            Q.push(MP(c,MP(x,y)));
        }
        cnt = ans = 0;
        REP(i,52) par[i]=i;
        while(cnt < n-1){
            edge tp = Q.top(); Q.pop();
            if(!isSame(tp.second.first, tp.second.second)){
                merge(tp.second.first, tp.second.second);
                ans += tp.first;
                cnt++;
            }
        }

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

    return 0;
}