2395:Out of Hay

PKU 蟻本

keyword

最小全域木　C++

概要

無向グラフが与えられる。最長辺が最小の木を作る問題。
木はgreedy。最小全域木を作ればよい。

typedef pair<int, pair<int,int> > pi;
int main(){
    int i, n, m, from, to, dist;
    n = readint(), m = readint();
    pi pis[10001];

    REP(i,n) pars[i] = i;
    REP(i,m){
        from = readint()-1;
        to = readint()-1;
        dist = readint();
        pis[i] = MP( dist, MP(from, to) );
    }
    sort(pis,pis+m);
    REP(i,m){
        pi tp = pis[i];
        if(!isSame(tp.sc.fs, tp.sc.sc)){
            merge(tp.sc.fs, tp.sc.sc);
            dist = tp.fs;
        }
    }

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

    return 0;
}