Spaghetti Source logo

最小全域有向木(Chu-Liu/Edmond)

説明

頂点 r を根とする最小全域有向木を求める.

アルゴリズムの概要は次のとおり.まず,各頂点に入る最小の辺だけからなるグラフを作る.このグラフが非巡回的であればこれは求める最小全域木である.巡回的ならば,その部分を一点に縮約し,辺コストを適切に修正し,再帰的に最小全域木を求める.求まった最小全域木に,縮約した部分を矛盾しないように展開していく.

計算量

O(V E).

ToDo

長すぎるので縮める.

なぜかこの実装は PKU では Runtime Error になる(逆辺グラフを作るところで破綻する).UVA で Accept するあたりたぶん PKU の入力が狂っているのだと思うが,原因を特定したい.

ソースコード

void backward_traverse(int v, int s, int r,
  graph &gg,
  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 = gg.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 (int k = 0; k < comp[s].size(); ++k) {
      int j = comp[s][k];
      if (j != r)
        for (int l = 0; l < gg[j].size(); ++l)
          if (no[ gg[j][l].src ] != s)
            gg[j][l].w -= mcost[ temp[j] ];
    }
  }
  mark[v] = true;
  for (int k = 0; k < next[v].size(); ++k) {
    int i = next[v][k];
    if (no[i] != no[v] && prev[ no[i] ] == v) 
      if (!mark[ no[i] ] || i == s)
        backward_traverse(i, s, r, gg,
            no, comp, prev, next, mcost, mark, cost, found);
  }
}
weight minimum_spanning_arborescence(int r, graph &g) {
  const int n = g.size();
  graph gg(n);
  for (int i = 0; i < g.size(); ++i)
    for (int j = 0; j < g[i].size(); ++j)
      gg[ g[i][j].dst ].push_back( g[i][j] );

  vector<int> no(n);
  vector< vector<int> > comp(n);
  for (int i = 0; i < n; ++i) {
    no[i] = i;
    comp[i].push_back(i);
  }
  weight cost = 0;
  while (1) {
    vector<int> prev(n, -1);
    vector<weight> mcost(n, inf);

    for (int j = 0; j < n; ++j) {
      if (j == r) continue;
      for (int k = 0; k < gg[j].size(); ++k) {
        int i = gg[j][k].src;
        if (no[i] != no[j]) {
          if (gg[j][k].w < mcost[ no[j] ]) {
            mcost[ no[j] ] = gg[j][k].w;
            prev[ no[j] ] = no[i];
          }
        }
      }
    }
    vector< vector<int> > next(n);
    for (int i = 0; i < n; ++i)
      if (prev[i] >= 0)
        next[ prev[i] ].push_back( i );

    bool stop = true;
    vector<int> mark(n);
    for (int i = 0; i < n; ++i) {
      if (i == r || mark[i] || comp[i].size() == 0) continue;
      bool found = false;
      backward_traverse(i, i, r, gg,
          no, comp, prev, next, mcost, mark, cost, found);
      if (found) stop = false;
    }
    if (stop) {
      for (int i = 0; i < n; ++i)
        if (prev[i] >= 0)
          cost += mcost[i];
      return cost;
    }
  }
}

Verified

補足

以下の実装は上のものを隣接行列で書き直したもの.PKU でも RE しない

void backward_traverse(int v, int s, int r, matrix &g,
  vector<int> &no, vector< vector<int> > &comp,
  vector<int> &prev, vector<weight> &mcost,
  vector<int> &mark, weight &cost, bool &found) {
  const int n = g.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 (int j = 0; j < n; ++j)
      if (j != r && no[j] == s)
        for (int i = 0; i < n; ++i)
          if (no[i] != s && g[i][j] < inf)
            g[i][j] -= mcost[ temp[j] ];
  }
  mark[v] = true;
  for (int i = 0; i < n; ++i)
    if (no[i] != no[v] && prev[ no[i] ] == v)
      if (!mark[ no[i] ] || i == s)
        backward_traverse(i, s, r, g,
            no, comp, prev, mcost, mark, cost, found);
}

weight minimum_spanning_arborescence(int r, matrix &g) {
  const int n = g.size();

  vector<int> no(n);
  vector< vector<int> > comp(n);
  for (int i = 0; i < n; ++i) {
    no[i] = i;
    comp[i].push_back(i);
  }
  weight cost = 0;
  while (1) {
    vector<int> prev(n, -1);
    vector<weight> mcost(n, inf);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (j == r) continue;
        if (no[i] != no[j] && g[i][j] < inf) {
          if (g[i][j] < mcost[ no[j] ]) {
            mcost[ no[j] ] = g[i][j];
            prev[ no[j] ] = no[i];
          }
        }
      }
    }
    bool stop = true;
    vector<int> mark(n);
    for (int i = 0; i < n; ++i) {
      if (i == r || mark[i] || comp[i].size() == 0) continue;
      bool found = false;
      backward_traverse(i, i, r, g,
          no, comp, prev, mcost, mark, cost, found);
      if (found) stop = false;
    }
    if (stop) {
      for (int i = 0; i < n; ++i)
        if (prev[i] >= 0)
          cost += mcost[i];
      return cost;
    }
  }
}

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.10.18 00:45:54.