CodeChef October Challenge 2019: Faulty System - 日々ｄｒｄｒする人のメモ

CodeChef October Challenge 2019の問題: Faulty System (Code: CNNCT2)
問題ページ: Contest Page | CodeChef

色々考えたけど、コンテスト中に解けなかった問題。
ずっと悩んでMatroid Intersectionを知らない人をした。

問題概要

$N$ 頂点と $M$ 個の無向辺が含まれる２つのグラフが与えられる。
2つのグラフの各頂点には $1$ から $N$ 、各辺には $1$ から $M$ の番号がついている。

2つのグラフについて、同じ番号の辺を用いて両方を連結グラフにしたい。
連結グラフにするために必要な最小辺数はいくらか？

制約

各テストケースに含まれるケース数: $1 \le T \le 1000$
$1 \le N, M \le 300$
各テストケース内において、 $M > 50$ となるケースは高々5つ
自己辺、多重辺は含まれない

解法

解説を読んだ。

CNNCT2 - Editorial - editorial - CodeChef Discuss

あとMatroid Intersectionまわりの解説も読んでちょっと理解した。

２つのグラフ $G_1, G_2$ のマトロイドを考え、Matroid Intersectionの問題として解く。

グラフ $G$ に対し、 $G - E'$ が連結グラフとなるような $E' \subseteq E$ を(マトロイドとしての)独立集合として考えた時、( $F$ をこの独立集合の族とすると) $M = (E, F)$ がマトロイドになることを利用して解を求められる。

別の方法として、2つのグラフにおけるgraphic matroidを利用しても求められる。２つのグラフが森となるように辺を選ぶ時の辺集合の最大サイズを求められるため、残りは各グラフで個別で辺を追加したものが解になる。

それぞれのマトロイドを $M_1 = (E, F_1), M_2 = (E, F_2)$ とする時 $I = \emptyset$ から以下の手順によって最大の独立集合 $I \in F_1 \cap F_2$ を求められる。

$I + x \in F_1 \cap F_2$ となる要素 $x$ がある限り貪欲に追加
2つのマトロイドに関するexchange graphを構築
- このグラフの頂点は $M$ 個あり、辺集合の各要素 $x \in E$ を表す
- , となる要素について
  - $I - x + y \in F_1$ であれば $x$ から $y$ への有向辺を追加
  - $I - x + y \in F_2$ であれば $y$ から $x$ への有向辺を追加
, となる集合について、
- このexchange graph上で $X_1$ の要素から $X_2$ の要素へのパスの中で最短となるパス(augmenting path)を求める
- パス中の $x \in I$ となる要素を $I$ から除去し、 $x \in E \setminus I$ となる要素を $I$ に追加する
- この更新の結果、 $I$ は独立集合のまま要素が一つ増える
再び (1) から処理を行い、要素が更新できなくなるまで繰り返す

実装

差集合で2つのグラフが連結となる辺集合がマトロイドを成すことを利用した実装

初めは全てのグラフを含んだ状態から、連結性を維持するように辺を削除していく。

計算量は $O(M^2(M+N))$

提出コード (C++14): Solution: 27717946 | CodeChef

#define N 301
#define M 301

int n, m;
vector<P> g1[N], g2[N];

bool cont[N];

// bridgeの計算
int b_used[N]; int val[N];
int dfs(int res[M], vector<P> g[N], int v, int p) {
  int cur = 0; bool mul = false;
  b_used[v] = 1;
  repe(&pr, g[v]) {
    int w = pr.first, j = pr.second;
    if(w == v || !cont[j]) {
      continue;
    }
    if(w == p) {
      if(mul) {
        ++cur;
        ++val[w];
      }
      mul = true;
      continue;
    }
    if(b_used[w] == 0) {
      int r = dfs(res, g, w, v);
      if(r == 0) {
        res[j] = 1;
      }
      cur += r;
    } else if(b_used[w] == 1) {
      ++cur;
      ++val[w];
    }
  }
  cur -= val[v];
  b_used[v] = 2;
  return cur;
}

void bridge(vector<P> g[N], int res[M]) {
  for(int i=0; i<n; ++i) b_used[i] = val[i] = 0;
  for(int i=0; i<m; ++i) res[i] = 0;
  dfs(res, g, 0, -1);
}

int b1[M], b2[M], bb1[M], bb2[M];

// exchange graph
vector<int> eg[M];

// exchange graph から augmenting path を求めて、
// (独立集合を維持するように)辺の状態をひっくり返す
int dist[M], prt[M];
bool find_augmenting_path() {
  queue<int> que;
  for(int i=0; i<m; ++i) dist[i] = -1;

  // 集合X1に含まれる頂点からの距離をBFSで計算 
  for(int i=0; i<m; ++i) {
    if(bb1[i]) {
      que.push(i);
      dist[i] = 0; prt[i] = -1;
    }
  }

  while(!que.empty()) {
    int v = que.front(); que.pop();
    for(int w : eg[v]) {
      if(dist[w] != -1) continue;

      dist[w] = dist[v] + 1;
      prt[w] = v;
      que.push(w);
    }
  }

  // X1 -> X2 となるpathの中で、最短となるpathを augmenting path とする
  int t = -1;
  for(int i=0; i<m; ++i) {
    if(!bb2[i] || dist[i] == -1) continue;

    if(t == -1 || dist[i] < dist[t]) {
      t = i;
    }
  }
  if(t == -1) {
    return false;
  }

  // 辺の状態をひっくり返す
  while(t != -1) {
    cont[t] ^= true;
    t = prt[t];
  }

  return true;
}

int main() {
  int t; cin >> t;
  while(t--) {
    cin >> n >> m;
    rep(i, n) g1[i].clear(), g2[i].clear();
    rep(i, m) {
      int u, v; cin >> u >> v; --u; --v;
      g1[u].emplace_back(P{v, i});
      g1[v].emplace_back(P{u, i});
    }
    rep(i, m) {
      int u, v; cin >> u >> v; --u; --v;
      g2[u].emplace_back(P{v, i});
      g2[v].emplace_back(P{u, i});
    }

    // 初期状態: 全ての辺が存在する
    rep(i, m) cont[i] = true;

    int ans = m;
    while(1) {

      // 各グラフの non-bridgeな辺 を求める
      bridge(g1, bb1);
      rep(i, m) bb1[i] = cont[i] && !bb1[i];
      bridge(g2, bb2);
      rep(i, m) bb2[i] = cont[i] && !bb2[i];


      bool updated = false;
      // 両方のグラフで non-bridgeな辺が存在する場合は消して再計算
      rep(i, m) {
        if(bb1[i] && bb2[i]) {
          --ans;
          cont[i] = false;
          updated = true;
          break;
        }
      }
      if(updated) continue;

      rep(i, m) eg[i].clear();

      rep(k, m) {
        if(cont[k]) continue;

        // 消した辺を一度復活させる (y ∈ E)
        cont[k] = true;

        // この状態でのnon-bridgeな辺 (x ∈ E)を求める
        // この non-bridgeな辺xを辺yを復活させながら消す (I + x - y)
        bridge(g1, b1);
        rep(i, m) b1[i] = cont[i] && !b1[i];
        bridge(g2, b2);
        rep(i, m) b2[i] = cont[i] && !b2[i];

        cont[k] = false;

        // exchange graph への辺の追加
        rep(i, m) {
          // I + x - y ∈ F_1 の時は 有向辺(y, x) を追加
          if(b1[i]) eg[k].push_back(i);
          // I + x - y ∈ F_2 の時は 有向辺(x, y) を追加
          if(b2[i]) eg[i].push_back(k);
        }
      }

      // augmenting path を計算
      // path に合わせて辺の状態をひっくり返し、辺を一つ消す
      if(!find_augmenting_path()) {
        break;
      }
      --ans;
    }
    cout << ans << endl;
  }
  return 0;
}

graphic matroidを利用する実装

初めは辺が存在しない状態から森を維持しながら辺を追加していく。

計算量は $O(NM(M+N))$

提出コード (C++14): Solution: 27722985 | CodeChef

#define N 301
#define M 301

int n, m;
vector<P> g1[N], g2[N];
int u1[M], v1[M], u2[M], v2[M];


bool cont[M];
int l1[M], l2[M];
bool conn1[M], conn2[M];

// 与えられたグラフに対し、同じ連結成分の頂点ごとに同じ色に塗った結果を返す
bool c_used[M];
void calc(vector<P> g[N], int label[N]) {
  rep(i, m) c_used[i] = false;
  int cur = 0;
  rep(i, n) {
    if(c_used[i]) continue;

    queue<int> que;
    c_used[i] = true;
    que.push(i);
    label[i] = cur;
    while(!que.empty()) {
      int v = que.front(); que.pop();
      repe(&pr, g[v]) {
        int w = pr.first, j = pr.second;
        if(c_used[w] || !cont[j]) continue;

        c_used[w] = true;
        que.push(w);
        label[w] = cur;
      }
    }
    ++cur;
  }
}

// exchange graph
vector<int> eg[M];

// exchange graph から augmenting path を求めて、
// (独立集合を維持するように)辺の状態をひっくり返す
int dist[M], prt[M];
bool find_augmenting_path() {
  queue<int> que;
  for(int i=0; i<m; ++i) dist[i] = -1;

  // 集合X1に含まれる頂点からの距離をBFSで計算 
  for(int i=0; i<m; ++i) {
    if(!conn1[i]) {
      que.push(i);
      dist[i] = 0; prt[i] = -1;
    }
  }

  while(!que.empty()) {
    int v = que.front(); que.pop();
    for(int w : eg[v]) {
      if(dist[w] != -1) continue;

      dist[w] = dist[v] + 1;
      prt[w] = v;
      que.push(w);
    }
  }

  // X1 -> X2 となるpathの中で、最短となるpathを augmenting path とする
  int t = -1;
  for(int i=0; i<m; ++i) {
    if(conn2[i] || dist[i] == -1) continue;

    if(t == -1 || dist[i] < dist[t]) {
      t = i;
    }
  }
  if(t == -1) {
    return false;
  }

  // 辺の状態をひっくり返す
  while(t != -1) {
    cont[t] ^= true;
    t = prt[t];
  }

  return true;
}

int main() {
  int t; cin >> t;
  while(t--) {
    cin >> n >> m;
    rep(i, n) g1[i].clear(), g2[i].clear();
    rep(i, m) {
      int u, v; cin >> u >> v; --u; --v;
      g1[u].emplace_back(P{v, i});
      g1[v].emplace_back(P{u, i});
      u1[i] = u; v1[i] = v;
    }
    rep(i, m) {
      int u, v; cin >> u >> v; --u; --v;
      g2[u].emplace_back(P{v, i});
      g2[v].emplace_back(P{u, i});
      u2[i] = u; v2[i] = v;
    }

    // 初期状態: 全ての辺が存在しない状態
    rep(i, m) cont[i] = false;
    int res = 0;

    while(1) {
      // 各グラフの連結状態を計算する
      calc(g1, l1);
      calc(g2, l2);

      rep(i, m) {
        conn1[i] = (l1[u1[i]] == l1[v1[i]]);
        conn2[i] = (l2[u2[i]] == l2[v2[i]]);
      }

      // 2つのグラフで、同じ辺が異なる連結成分を結んでいる辺があれば追加して再計算
      bool updated = false;
      rep(i, m) {
        if(!conn1[i] && !conn2[i]) {
          cont[i] = true;
          updated = true;
          ++res;
          break;
        }
      }
      if(updated) continue;

      rep(i, m) eg[i].clear();

      rep(k, m) {
        if(!cont[k]) continue;
        // 追加した辺を一度消す (y ∈ E)
        cont[k] = false;

        // この状態で連結の状態を計算
        // 異なる連結成分を結ぶ辺(x ∈ E)を辺yを消す代わりに追加する (I + x - y)
        calc(g1, l1);
        calc(g2, l2);

        cont[k] = true;

        // exchange graphへの辺の追加
        rep(i, m) {
          // I + x - y ∈ F_1 の時は 有向辺(y, x) を追加
          if(l1[u1[i]] != l1[v1[i]]) eg[k].push_back(i);
          // I + x - y ∈ F_2 の時は 有向辺(x, y) を追加
          if(l2[u2[i]] != l2[v2[i]]) eg[i].push_back(k);
        }
      }

      // augmenting path を計算
      // (奇数長の) path に合わせて辺の状態をひっくり返し、辺を一つ追加する
      if(!find_augmenting_path()) {
        break;
      }
      ++res;
    }

    // 2*(連結成分の数) + (2つのグラフで共通で追加できた辺の数)
    cout << 2*(n - 1 - res) + res << endl;
  }
  return 0;
}