Algoogle

Algorithm for Programming Contest

Prim法

基本情報


計算量
用途 最小全域木を求める

E := 辺の数
V := 頂点数

解説


すでに到達した頂点の集合からまだ到達していない頂点の集合への辺のうち, コストが最小のものを選んでいくことで最小全域木を構成する.
Dijkstra法と似ている.

コード


(prim.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef pair<int,int> pii; // (cst, to)
vector<pii> G[MAX];
bool used[MAX];

int prim() {
    priority_queue<pii, vector<pii>, greater<pii> > que;
    memset(used, 0, sizeof(used));
    que.push(pii(0,0));
    int ret = 0;
    while(!que.empty()) {
        int cst = que.top().first, v = que.top().second;
        que.pop();
        if(used[v]) continue;
        used[v] = 1;
        ret += cst;
        for(int i = 0; i < G[v].size(); i++)
            que.push(pii(G[v][i].first, G[v][i].second));
    }
    return ret;
}

問題


Comments