POJ1258: Agri-Net

概要

最小全域木を求める.

typedef int Weight;
struct Edge{
    int from, to;
    Weight weight;
    Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
bool operator< (const Edge &a, const Edge &b){
    return a.weight > b.weight;
}

pair<Weight, Edges> prim(const Graph &g, int s){
    int n = g.size();
    Edges es;
    Weight res = 0;

    vector<bool> visited(n);
    priority_queue<Edge> Q;
    Q.push(Edge(-1, s, 0));
    while(!Q.empty()){
        Edge e = Q.top(); Q.pop();
        if(visited[e.to]) continue;
        es.push_back(e);
        res += e.weight;
        visited[e.to] = true;
        EACH(i, g[e.to]) if(!visited[i->to]) Q.push(*i);
    }
    return make_pair(res, es);
}
int N;
int main(){
    while(~scanf("%d", &N)){
        Graph g(N);
        for(int i = 0; i < N; ++i)for(int j = 0; j < N; ++j){
            int v;
            scanf("%d", &v);
            g[i].push_back(Edge(i, j, v));
        }
        EACH(i, g){
            EACH(j, *i){
            }
        }
        printf("%d\n", prim(g, 0).first);
    }
    return 0;
}