http://www.prefield.com/algorithm/index.html
こちらのサイトにある「各種アルゴリズムのC++による実装」の使い方について知りたく、質問させていただきました。
グラフ、全域木のところにある「最小全域有向木」のプログラムの使い方がわからず困っております。
ソースコードは
・テンプレート
C++
1#define _GLIBCXX_DEBUG 2#include <iostream> 3#include <vector> 4 5using namespace std; 6 7#define REP(i,n) for(int i=0;i<(int)n;++i) 8#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) 9#define ALL(c) (c).begin(), (c).end() 10 11int main() { 12 13}
・最小全域有向木
C++
1void visit(Graph &h, int v, int s, int r, 2 vector<int> &no, vector< vector<int> > &comp, 3 vector<int> &prev, vector< vector<int> > &next, vector<Weight> &mcost, 4 vector<int> &mark, Weight &cost, bool &found) { 5 const int n = h.size(); 6 if (mark[v]) { 7 vector<int> temp = no; 8 found = true; 9 do { 10 cost += mcost[v]; 11 v = prev[v]; 12 if (v != s) { 13 while (comp[v].size() > 0) { 14 no[comp[v].back()] = s; 15 comp[s].push_back(comp[v].back()); 16 comp[v].pop_back(); 17 } 18 } 19 } while (v != s); 20 FOR(j,comp[s]) if (*j != r) FOR(e,h[*j]) 21 if (no[e->src] != s) e->weight -= mcost[ temp[*j] ]; 22 } 23 mark[v] = true; 24 FOR(i,next[v]) if (no[*i] != no[v] && prev[no[*i]] == v) 25 if (!mark[no[*i]] || *i == s) 26 visit(h, *i, s, r, no, comp, prev, next, mcost, mark, cost, found); 27} 28Weight minimumSpanningArborescence(const Graph &g, int r) { 29 const int n = g.size(); 30 Graph h(n); 31 REP(u,n) FOR(e,g[u]) h[e->dst].push_back(*e); 32 33 vector<int> no(n); 34 vector< vector<int> > comp(n); 35 REP(u, n) comp[u].push_back(no[u] = u); 36 37 for (Weight cost = 0; ;) { 38 vector<int> prev(n, -1); 39 vector<Weight> mcost(n, INF); 40 41 REP(j,n) if (j != r) FOR(e,g[j]) 42 if (no[e->src] != no[j]) 43 if (e->weight < mcost[ no[j] ]) 44 mcost[ no[j] ] = e->weight, prev[ no[j] ] = no[e->src]; 45 46 vector< vector<int> > next(n); 47 REP(u,n) if (prev[u] >= 0) 48 next[ prev[u] ].push_back(u); 49 50 bool stop = true; 51 vector<int> mark(n); 52 REP(u,n) if (u != r && !mark[u] && !comp[u].empty()) { 53 bool found = false; 54 visit(h, u, u, r, no, comp, prev, next, mcost, mark, cost, found); 55 if (found) stop = false; 56 } 57 if (stop) { 58 REP(u,n) if (prev[u] >= 0) cost += mcost[u]; 59 return cost; 60 } 61 } 62}
と書いてありました。
最小全域有向木を求めるプログラムを使うために自分で用意しなければならない変量はどれでしょうか?またどういった形式の変量を用意すれば良いのでしょうか?
よろしくお願いいたします。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2015/12/07 06:33