This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// プリム法 (最小全域木問題)
// 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)