[ARC165] C - Social Distance on Graph

[Q] https://atcoder.jp/contests/arc165/tasks/arc165_c

考察
0. 同じ色の頂点を結ぶすべてのパスのうち、最もコストの低いパスを最大化したい。
1. 適当に色を塗ってみると、3辺以上とるパスがないことに気づく。R-B-Rみたいな2辺またぎが最大。
2. 二部グラフで塗ることができれば最善で、各頂点ごとに、コストの低い2辺の和を見て、最小値をとればいい。

3. そうはいかない場合がある。辺のコストが小さい順番に辺を張っていって、二部グラフが成り立たなくなる辺を見つける。
二部グラフが成り立たなくなる辺の両端は同じ色。二部グラフが成り立たなくなる辺は単独でとることになる。
4. 二分探索で、単独辺を見つけることができそうだ。

5. 答えは、4.で見つけた単独辺か、各頂点からコストが低い2辺を足したもののうち、小さいほうが答えになる。

実装

int main() {
  cincout();

  ll N, M;
  cin >> N >> M;
  vector<tll> V(M); // w, a, b
  rep(i, M) {
    ll a, b, w;
    cin >> a >> b >> w;
    --a;
    --b;
    V[i] = {w, a, b};
  }
  // M本の辺は、コストが軽い順番に並べる
  sort(all(V));

  // trueのとき、二部グラフができる
  auto make_graph = [&](vector<ll> &color, vector<vector<pll>> &g, ll mid) -> bool {
    rep(i, mid) {
      auto [w, a, b] = V[i];
      g[a].emplace_back(w, b);
      g[b].emplace_back(w, a);
    }
    rep(i, N) {  // 色うめ
      if (color[i] != -1) continue;
      color[i] = 0;  // 0 or 1
      queue<pll> Q;
      Q.emplace(i, -1);
      while (!Q.empty()) {
        auto [v, p] = Q.front();
        Q.pop();
        for (auto [w, u] : g[v]) {
          if (u == p) continue;
          if (color[v] == color[u]) return false;
          if (color[u] != -1) continue;
          color[u] = 1 ^ color[v];
          Q.emplace(u, v);
        }
      }
    }
    return true;
  };

  // 二部グラフができなくなるXを見つける
  auto nibutan = [&](ll idxl,
                     ll idxr) -> ll {
    while (idxr - idxl > 1) {
      ll mid = (idxl + idxr) / 2;
      vector<ll> color(N, -1);
      vector<vector<pll>> g(N, vector<pll>());

      if (make_graph(color, g, mid)) {
        idxl = mid;
      } else {
        idxr = mid;
      }
    }
    return idxl;
  };
  ll idx = nibutan(0, M + 1);
  ll ans = oo;
  // 二部グラフができない辺の両端は同じ色。解答候補
  if (idx < M){
    chmin(ans, get<0>(V[idx]));
  }
  // あとは、各頂点ごとに、コストの低い2本を結んだ値を見る
  vector<ll> color(N, -1);
  vector<vector<pll>> g(N, vector<pll>());
  make_graph(color, g, idx);
  rep(i, N) {
    if (g[i].size() < 2) continue;
    // ある頂点から見て、コストの低い2本を結んだ値だけが答えになりうる
    chmin(ans, g[i][0].first + g[i][1].first);
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/arc165/submissions/45693010