らての精進日記

修行をします

aoj0072:Carden Lantern

解法

明らかに与えられたグラフの最少全域木を求めればよいことがわかる。最少全域木を求めるアルゴリズムとしてPrim法やKruskal法などが知られている。

Prim法はpriority_queueを使ってDijkstra法っぽく最少全域木を求める。
Kruskal法はunion_findを使って最少全域木を求める。

Prim法で解けるときには大体Kruskal法でも解けるのでKruskal法しか僕は書かないが、Prim法が必要になるときは来るのだろうか・・・

コード

#include<bits/stdc++.h>
using namespace std;

struct UF{
    vector<int>par,sz;
    int N;
    UF(int _N){
        N=_N;
        par=sz=vector<int>(N,1);
        for(int i=0;i<N;i++)par[i]=i;
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        par[y]=x;
        sz[x]+=sz[y];
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
};

struct edge{
    int u,v,cost;
    edge(int a,int b,int c):u(a),v(b),cost(c){}
    edge(){}
};

bool operator<(const edge &a,const edge &b){
    return a.cost<b.cost;
}

int n,m;

void solve(){
    vector<edge>es;
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d,%d,%d",&a,&b,&c);
        es.push_back(edge(a,b,c/100-1));
    }
    sort(es.begin(),es.end());

    UF uf(n);
    int ans=0;

    for(int i=0;i<m;i++){
        edge &e=es[i];
        if(uf.same(e.u,e.v))continue;
        uf.unite(e.u,e.v);
        ans+=e.cost;
    }

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

int main(){
    while(scanf("%d",&n),n)solve();
    return 0;
}