IOI 2008 Egypt過去問 ISLANDS - TopCoderとJ言語と時々F#

問題概要

N個の頂点とN個の辺を持ち、どの頂点も最低1つの辺で接続されているような重み付き無向グラフが与えられる。好きな頂点から出発して、次のどちらかの移動を繰り返す。ただし同じ頂点に2度訪れることはできない。

辺を辿って移動する。
どのように辺を辿っても移動できないような頂点にワープする。

このとき、通った辺の重みの和を最大化せよ。

2 <= N <= 1,000,000
1 <= 辺重み <= 100,000,000

解法

まず問題は連結成分ごとに分解できるので、連結成分ごとに最大重みの経路を求める問題を解いてすべて合計すればよい。

ここでグラフに課せられた制約(孤立点が存在しない)から、全ての連結成分は頂点数と辺数が等しい。よってこの連結成分は木に1本だけ辺を追加した形をしている。見方を変えれば、この連結成分にはサイクルが1つだけ存在する。

さて、このサイクルについて考えたい。サイクルの頂点を (v[1], v[2], ..., v[c]) として、ある頂点 v[k] に注目する。v[k] から v[k-1] と v[k+1] への辺を切ると、そこには v[k] を根とする木が残る。つまりサイクルは c 個の根付き木の根同士が繋がってできたものと見なすことができる。

このことから最適解は、次のいずれかになる。

サイクルの頂点のうちどれかを根とする木の直径
サイクルのある2頂点 s, t を根とする木の高さと、サイクル中における s, t の距離の和

後者のイメージとしては、 s を根とする木の葉から根である s へと辿り、そこからサイクルを s から t へ辿り、最後に t からその木の葉まで辿るという感じになる。

あとは、後者の方を計算するときに愚直に実装するとサイクルの頂点数を c とすれば O(c^2) 時間が必要になってしまうので注意が必要。v[k]を根とする木の高さを height[k] として、v[1]からv[2], v[3], ... と辿ってv[k]まで到達する時の距離を len[k]、そしてサイクル中の辺重みの総和を L とすると後者は

max(i < j) { height[i] + height[j] + max(v[j]-v[i], L-(v[j]-v[i])) }

を計算することで求められるがこの式を変形して

max {
  max(i < j) { height[i] + height[j] + v[j] - v[i] },
  L + max(i < j) { height[i] + height[j] - v[j] + v[i] }
}

とし、さらに

max {
  max(i < j) { (height[i] - v[i]) + (height[j] + v[j]) },
  L + max(i < j) { (height[i] + v[i]) + (height[j] - v[j]) }
}

と考えればi, jが分離できたので O(c) で計算可能になる。

以上を全てまとめると、全て頂点数について線形時間なので全体で O(N)。

ソース

という以上の解法を実装したけど2秒が切れない。 isl19g.in あたりで3秒ちょっとかかってしまう。実装が下手すぎる模様。

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct edge {
  int src, dst, len, id;
  edge(int s, int d, int l, int i)
    : src(s), dst(d), len(l), id(i) { }
};
typedef vector<edge> vertex;
typedef vector<vertex> graph;

void get_cc_dfs(const graph& g, int v, vector<int>& ids, int k)
{
  if(ids[v] >= 0) return;
  ids[v] = k;
  for(int i=0; i<g[v].size(); ++i)
    get_cc_dfs(g, g[v][i].dst, ids, k);
}

vector<graph> get_connected_components(const graph& g)
{
  const int n = g.size();
  vector<graph> ret;
  vector<int> ids(n, -1);
  for(int i=0; i<n; ++i) ids[i] = -1;
  int cnt = 0;
  for(int i=0; i<n; ++i)
    if(ids[i] == -1)
      get_cc_dfs(g, i, ids, cnt++);
  vector<int> new_id_pools(cnt, 0);
  vector<int> new_ids(n);
  for(int i=0; i<n; ++i)
    new_ids[i] = new_id_pools[ids[i]]++;
  ret.resize(cnt);
  for(int i=0; i<cnt; ++i)
    ret[i] = graph(new_id_pools[i]);
  for(int i=0; i<n; ++i)
    for(int j=0; j<g[i].size(); ++j)
      ret[ids[i]][new_ids[i]].push_back(edge(new_ids[i], new_ids[g[i][j].dst], g[i][j].len, g[i][j].id));
  return ret;
}

int get_cycle_dfs(const graph& g, int v, int prev, vector<bool>& vis, vector<int>& cycle)
{
  if(vis[v]) return v;
  vis[v] = true;
  int ret = -1;
  for(int i=0; i<g[v].size(); ++i) {
    if(g[v][i].id != prev) {
      int k = get_cycle_dfs(g, g[v][i].dst, g[v][i].id, vis, cycle);
      if(k < -1) return -2;
      if(k >= 0) {
	cycle.push_back(v);
	ret = k;
	if(ret == v) return -2;
      }
    }
  }
  return ret == v ? -2 : ret;
}

vector<int> get_cycle(const graph& g)
{
  const int n = g.size();
  vector<bool> vis(n, false);
  vector<int> ret;
  get_cycle_dfs(g, 0, -1, vis, ret);
  return ret;
}

long long get_cyclepath_len(const graph& g, const vector<int>& cycle, vector<long long>& cpath_len)
{
  const int m = cycle.size();
  cpath_len.resize(m, 0);
  long long cpath_sum = 0;
  for(int i=0; i<m; ++i) {
    int next = cycle[(i+1)%m];
    for(int j=0; j<g[cycle[i]].size(); ++j) {
      if(g[cycle[i]][j].dst == next) {
	cpath_len[(i+1)%m] = g[cycle[i]][j].len;
	cpath_sum += g[cycle[i]][j].len;
      }
    }
  }
  cpath_len[0] = 0;
  for(int i=1; i<m; ++i)
    cpath_len[i] += cpath_len[i-1];
  if(cycle.size() == 2) cpath_sum >>= 1;
  return cpath_sum;
}

long long calc_max_height_dfs(const graph& g, int v, int prev)
{
  long long ret = 0;
  for(int i=0; i<g[v].size(); ++i)
    if(g[v][i].dst != prev)
      ret = max(ret, calc_max_height_dfs(g, g[v][i].dst, v) + g[v][i].len);
  return ret;
}

vector<long long> calc_max_height(const graph& g, const vector<int>& cycle)
{
  const int m = cycle.size();
  vector<long long> ret(m, 0);
  for(int i=0; i<m; ++i) {
    int prev = cycle[(i+m-1)%m], next = cycle[(i+1)%m];
    for(int j=0; j<g[cycle[i]].size(); ++j)
      if(g[cycle[i]][j].dst != prev && g[cycle[i]][j].dst != next)
	ret[i] = max(ret[i], calc_max_height_dfs(g, g[cycle[i]][j].dst, cycle[i]) + g[cycle[i]][j].len);
  }
  return ret;
}

pair<long long, int> calc_diameter_dfs(const graph& g, int v, int prev, int no1, int no2)
{
  pair<long long, int> ret(0, v);
  for(int i=0; i<g[v].size(); ++i) {
    edge e = g[v][i];
    if(e.dst != prev && e.dst != no1 && e.dst != no2) {
      pair<long long, int> tmp = calc_diameter_dfs(g, e.dst, v, no1, no2);
      tmp.first += e.len;
      if(ret.first < tmp.first) ret = tmp;
    }
  }
  return ret;
}

vector<long long> calc_diameters(const graph& g, const vector<int>& cycle)
{
  const int m = cycle.size();
  vector<long long> ret;
  for(int i=0; i<m; ++i) {
    int prev = cycle[(i+m-1)%m], next = cycle[(i+1)%m];
    pair<long long, int> a, b;
    a = calc_diameter_dfs(g, cycle[i], -1, prev, next);
    b = calc_diameter_dfs(g, a.second, -1, prev, next);
    ret.push_back(b.first);
  }
  return ret;
}

long long solve(const graph& g)
{
  if(g.size() == 1) return 0;
  vector<int> cycle = get_cycle(g);
  const int m = cycle.size();
  
  vector<long long> cpath_len;
  long long cpath_sum = get_cyclepath_len(g, cycle, cpath_len);
  vector<long long> max_height = calc_max_height(g, cycle);
  vector<long long> diameters = calc_diameters(g, cycle);

  long long ret = *max_element(diameters.begin(), diameters.end());
  long long partial_max = max_height.back() + cpath_len.back();
  for(int i=m-2; i>=0; --i) {
    ret = max(ret, max_height[i] - cpath_len[i] + partial_max);
    partial_max = max(partial_max, max_height[i] + cpath_len[i]);
  }
  partial_max = max_height.back() - cpath_len.back();
  for(int i=m-2; i>=0; --i) {
    ret = max(ret, cpath_sum + max_height[i] + cpath_len[i] + partial_max);
    partial_max = max(partial_max, max_height[i] - cpath_len[i]);
  }
  return ret;
}

int main()
{
  int N;
  graph G;
  scanf("%d", &N);
  G = graph(N);
  for(int i=0; i<N; ++i) {
    int d, l;
    scanf("%d%d", &d, &l);
    d--;
    G[i].push_back(edge(i, d, l, i));
    G[d].push_back(edge(d, i, l, i));
  }
  vector<graph> cc = get_connected_components(G);
  long long sol = 0;
  for(int i=0; i<cc.size(); ++i)
    sol += solve(cc[i]);
  printf("%lld\n", sol);
  return 0;
}