graph/graph_004_prim.cpp

• View this file on GitHub
• Last update: 2019-11-22 21:50:52+09:00

Code

// プリム法 (最小全域木問題)

// Edgeには from, to, cost の情報が必須。計算量 O( |V|^2 )

// → priority_queueを用いて、O( |E| log|V| )！

// ここに書いてあるのは勿論オーダー小さい方の実装です。


// 最小全域木(無向)

// Verified: AOJ GRL_2_A: Minimum Spanning Tree

template <typename T>
T prim(vector< vector< Edge<T> > > &G) {
    int V = G.size(); T ans = 0;
    vector<bool> used(V, false);
    priority_queue< Edge<T>, vector< Edge<T> >, greater< Edge<T> > > q;
    q.push(Edge<T>(0, 0, 0));
    while(!q.empty()) {
        Edge<T> temp = q.top(); q.pop();
        if(used[temp.to]) continue;
        used[temp.to] = true;
        ans += temp.cost;
        for(size_t i=0; i<G[temp.to].size(); i++) q.push(G[temp.to][i]);
    }
    return ans;
}

// 最小全域木(無向) 重みと辺集合のペアで返すよ！

template <typename T>
pair<int, vector< Edge<T> > > prim(vector< vector< Edge<T> > > &G) {
    int V = G.size(); T ans = 0;
    vector< Edge<T> > ans_e;
    vector<bool> used(V, false);
    priority_queue< Edge<T>, vector< Edge<T> >, greater< Edge<T> > > q;
    q.push(Edge<T>(-1, 0, 0));
    while(!q.empty()) {
        Edge<T> temp = q.top(); q.pop();
        if(used[temp.to]) continue;
        used[temp.to] = true;
        ans += temp.cost; if(temp.from >= 0) ans_e.push_back(temp);
        for(size_t i=0; i<G[temp.to].size(); i++) q.push(G[temp.to][i]);
    }
    // 全域木作れないなら答えを INF にする

    for(int i=0; i<V; i++) if(!used[i]) ans = numeric_limits<T>::max();
    return pair<int, vector< Edge<T> > >(ans, ans_e);
}

// 最小全域有向木 (有向)

// (Under construction)

#line 1 "graph/graph_004_prim.cpp"
// プリム法 (最小全域木問題)

// Edgeには from, to, cost の情報が必須。計算量 O( |V|^2 )

// → priority_queueを用いて、O( |E| log|V| )！

// ここに書いてあるのは勿論オーダー小さい方の実装です。


// 最小全域木(無向)

// Verified: AOJ GRL_2_A: Minimum Spanning Tree

template <typename T>
T prim(vector< vector< Edge<T> > > &G) {
    int V = G.size(); T ans = 0;
    vector<bool> used(V, false);
    priority_queue< Edge<T>, vector< Edge<T> >, greater< Edge<T> > > q;
    q.push(Edge<T>(0, 0, 0));
    while(!q.empty()) {
        Edge<T> temp = q.top(); q.pop();
        if(used[temp.to]) continue;
        used[temp.to] = true;
        ans += temp.cost;
        for(size_t i=0; i<G[temp.to].size(); i++) q.push(G[temp.to][i]);
    }
    return ans;
}

// 最小全域木(無向) 重みと辺集合のペアで返すよ！

template <typename T>
pair<int, vector< Edge<T> > > prim(vector< vector< Edge<T> > > &G) {
    int V = G.size(); T ans = 0;
    vector< Edge<T> > ans_e;
    vector<bool> used(V, false);
    priority_queue< Edge<T>, vector< Edge<T> >, greater< Edge<T> > > q;
    q.push(Edge<T>(-1, 0, 0));
    while(!q.empty()) {
        Edge<T> temp = q.top(); q.pop();
        if(used[temp.to]) continue;
        used[temp.to] = true;
        ans += temp.cost; if(temp.from >= 0) ans_e.push_back(temp);
        for(size_t i=0; i<G[temp.to].size(); i++) q.push(G[temp.to][i]);
    }
    // 全域木作れないなら答えを INF にする

    for(int i=0; i<V; i++) if(!used[i]) ans = numeric_limits<T>::max();
    return pair<int, vector< Edge<T> > >(ans, ans_e);
}

// 最小全域有向木 (有向)

// (Under construction)

Back to top page