![見出し画像](https://assets.st-note.com/production/uploads/images/116506529/rectangle_large_type_2_82bf2f509dcd0d26d9f579ac049c5b68.png?width=1200)
Photo by
t0m0y0
[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;
}
この記事が気に入ったらサポートをしてみませんか?