質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.78%

こちらのサイトにある「各種アルゴリズムのC++による実装」の使い方について

受付中

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 1,511

score 8

http://www.prefield.com/algorithm/index.html こちらのサイトにある「各種アルゴリズムのC++による実装」の使い方について知りたく、質問させていただきました。

グラフ、全域木のところにある「最小全域有向木」のプログラムの使い方がわからず困っております。

ソースコードは

・テンプレート

#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

int main() {

}

・最小全域有向木

void visit(Graph &h, int v, int s, int r,
  vector<int> &no, vector< vector<int> > &comp,
  vector<int> &prev, vector< vector<int> > &next, vector<Weight> &mcost,
  vector<int> &mark, Weight &cost, bool &found) {
  const int n = h.size();
  if (mark[v]) {
    vector<int> temp = no;
    found = true;
    do {
      cost += mcost[v];
      v = prev[v];
      if (v != s) {
        while (comp[v].size() > 0) {
          no[comp[v].back()] = s;
          comp[s].push_back(comp[v].back());
          comp[v].pop_back();
        }
      }
    } while (v != s);
    FOR(j,comp[s]) if (*j != r) FOR(e,h[*j])
      if (no[e->src] != s) e->weight -= mcost[ temp[*j] ];
  }
  mark[v] = true;
  FOR(i,next[v]) if (no[*i] != no[v] && prev[no[*i]] == v)
    if (!mark[no[*i]] || *i == s)
      visit(h, *i, s, r, no, comp, prev, next, mcost, mark, cost, found);
}
Weight minimumSpanningArborescence(const Graph &g, int r) {
  const int n = g.size();
  Graph h(n);
  REP(u,n) FOR(e,g[u]) h[e->dst].push_back(*e);

  vector<int> no(n);
  vector< vector<int> > comp(n);
  REP(u, n) comp[u].push_back(no[u] = u);

  for (Weight cost = 0; ;) {
    vector<int> prev(n, -1);
    vector<Weight> mcost(n, INF);

    REP(j,n) if (j != r) FOR(e,g[j])
      if (no[e->src] != no[j])
        if (e->weight < mcost[ no[j] ])
          mcost[ no[j] ] = e->weight, prev[ no[j] ] = no[e->src];

    vector< vector<int> > next(n);
    REP(u,n) if (prev[u] >= 0)
      next[ prev[u] ].push_back(u);

    bool stop = true;
    vector<int> mark(n);
    REP(u,n) if (u != r && !mark[u] && !comp[u].empty()) {
      bool found = false;
      visit(h, u, u, r, no, comp, prev, next, mcost, mark, cost, found);
      if (found) stop = false;
    }
    if (stop) {
      REP(u,n) if (prev[u] >= 0) cost += mcost[u];
      return cost;
    }
  }
}

と書いてありました。

最小全域有向木を求めるプログラムを使うために自分で用意しなければならない変量はどれでしょうか?またどういった形式の変量を用意すれば良いのでしょうか?

よろしくお願いいたします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

+1

ざっと見てみました。 アルゴリズムの中身は全く分かりませんが、下記のことが分かりました。

まず、問題はこれですね?

重み付き有向グラフG(V,E) について、頂点rを根とする最小全域有向木の辺の重みの総和を求めて下さい。

であれば、下記がこの問題を解く関数ではないかと思います。

Weight minimumSpanningArborescence(const Graph &g, int r)

Graphが重み付き有向グラフG(V,E)、rが頂点r、「戻り値が最小全域有向木の辺の重みの総和」だろうと思います。 本当にそうなのかはこのサイトの著者に聞くしかないですが。

Graph型はここで定義されてます。
恐らく、Graph g;の時、g[i]が頂点iの情報で、g[i]は「頂点iを始点とする辺の情報をリストとして格納」しているのだと思います。
つまり、型Edgesが頂点の型ですね。EdgesはEdge(辺)の集まりであり、かつ、GraphはEdgesの集まりになってますから。

ということは、Graph gを適切に定義して頂点rを決めて、minimumSpanningArborescence()を呼び出せば、答えを計算してくれそうです。

下記イメージですね。ここの入力例1のケースで書いてます。

Graph g;

// 頂点0
Edges p0;
p0.push_back(0, 1, 3);
p0.push_back(0, 2, 2);
g.push_back(p0);

// 頂点1
Edges p1;
g.push_back(p1);

// 頂点2
Edges p2;
p2.push_back(2, 0, 1);
p2.push_back(2, 3, 1);
g.push_back(p2);

// 頂点3
Edges p2;
p3.push_back(3, 0, 1);
p3.push_back(3, 1, 5);
g.push_back(p3);

std::cout << "result=" << minimumSpanningArborescence(g, 0);

かなり推測を含んでます。また、上記はコンパイルもしてませんので、それなりに間違いがあるかも知れません。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/12/07 15:33

    ありがとうございました。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.78%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る