Задача [B-A'] 4: Игра на графе Условие задачи (pdf...
Created on: September 3, 2025
Answered using GPT-5 Thinking by Chat01
Question
Задача [B-A'] 4: Игра на графе
Условие задачи (pdf)
Дан неориентированный взвешенный связный граф из
n
вершин и
m
ребер.
Никита и Миша играют в игру. Сначала Никита красит каждую вершину графа в один из двух цветов (в том числе разрешается покрасить все вершины в один цвет). После этого Миша выбирает две различные вершины
s
и
t
, покрашенные Никитой в одинаковый цвет. Результатом игры считается расстояние между вершинами
s
и
t
в графе (минимальная сумма весов ребер на пути между
s
и
t
).
Никита стремится максимизировать итоговый результат, а Миша — минимизировать. Найдите итоговый результат игры, если Никита и Миша играют оптимально.
Формат входных данных
Первая строка содержит два целых числа
n
и
m
(
3
≤
n
≤
200
000
,
n
−
1
≤
m
≤
min
(
n
(
n
−
1
)
2
,
200
000
)
) — количество вершин и ребер графа соответственно.
Следующие
m
строк содержат три целых числа
u
,
v
и
w
(
1
≤
u
<
v
≤
n
,
1
≤
w
≤
10
9
), задающих неориентированное ребро между вершинами
u
и
v
веса
w
.
Гарантируется, что граф является связным и все пары
(
u
,
v
)
попарно различны.
Формат выходных данных
Выведите итоговый результат игры при условии, что оба игрока играют оптимально.
Примеры
Входные данные
3 3
1 2 3
2 3 4
1 3 8
Выходные данные
7
Примечания
Пусть Никита покрасил вершины с номерами
1
и
3
в одинаковый цвет, а вершину с номером
2
— в другой цвет. Миша же, в свою очередь, может выбрать
s
1
и
t
3
. Расстояние между этими вершинами равняется
7
.
Можно показать, что Никита не может гарантировать себе больший ответ, поэтому результат игры равняется
7
.
(Дай мне код решения этой задачи на c++)
Thought
Answer
Вот надёжное решение на C++ (O(m log m)), основанное на двух ключевых наблюдениях:
- Пусть D — искомый ответ. Построим граф H(D), где вершины те же, а ребро между u и v есть тогда и только тогда, когда dist(u, v) < D. Требуется, чтобы H(D) был двудольным. Минимальное D, при котором H(D) перестаёт быть двудольным, равно минимуму из:
- A — минимальный порог, при котором среди рёбер с весом < D появляется нечётный цикл (находим DSU с паритетами, добавляя рёбра по возрастанию веса — первый конфликт и даёт A);
- B — минимальное расстояние между двумя вершинами, кратчайший путь между которыми использует ≥2 ребра. Это достигается на пути из ровно двух рёбер, значит B = min по вершине v (сумма двух наименьших весов рёбер, инцидентных v).
Ответ = min(A, B).
cpp#include <bits/stdc++.h> using namespace std; struct DSU { int n; vector<int> p, r, xr; // xr[u] = parity(u, root) DSU(int n=0): n(n), p(n+1), r(n+1,0), xr(n+1,0) { iota(p.begin(), p.end(), 0); } pair<int,int> findp(int a){ // returns (root, parity to root) if(p[a]==a) return {a,0^xr[a]}; // xr[a] stored to parent; to root accumulate below auto pr = findp(p[a]); xr[a] ^= xr[p[a]]; p[a] = pr.first; return {p[a], xr[a]}; } // enforce color[a] ^ color[b] = val (val=0 same, 1 different) // returns false if contradiction bool unite(int a, int b, int val){ auto [ra, xa] = findp(a); auto [rb, xb] = findp(b); if(ra == rb){ // need xa ^ xb == val return ((xa ^ xb) == val); } if(r[ra] < r[rb]) { swap(ra, rb); swap(xa, xb); } // attach rb under ra; we need (color[a] ^ xa) ^ (color[b] ^ xb) == val // => color[rbRoot] parity to ra should be xa ^ xb ^ val p[rb] = ra; xr[rb] = xa ^ xb ^ val; if(r[ra] == r[rb]) r[ra]++; return true; } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; if(!(cin >> n >> m)) return 0; struct Edge{int u,v; long long w;}; vector<Edge> edges(m); vector<vector<pair<int,long long>>> adj(n+1); for(int i=0;i<m;i++){ int u,v; long long w; cin >> u >> v >> w; edges[i] = {u,v,w}; adj[u].push_back({v,w}); adj[v].push_back({u,w}); } // Compute A: minimal max edge weight on an odd cycle (among original edges) long long INF = (long long)4e18; long long A = INF; { vector<Edge> e = edges; sort(e.begin(), e.end(), [](const Edge& a, const Edge& b){ if(a.w != b.w) return a.w < b.w; return a.u < b.u; }); DSU dsu(n); for(const auto& ed : e){ // constraint: colors[u] ^ colors[v] = 1 if(!dsu.unite(ed.u, ed.v, 1)){ A = ed.w; // first conflict weight break; } } } // Compute B: minimal distance realized by path of >=2 edges. // It suffices to take the minimal sum of two smallest incident edge weights at the same vertex. long long B = INF; for(int v=1; v<=n; v++){ if(adj[v].size() < 2) continue; long long m1 = INF, m2 = INF; for(auto [to,w] : adj[v]){ if(w < m1){ m2 = m1; m1 = w; } else if(w < m2){ m2 = w; } } if(m2 < INF) B = min(B, m1 + m2); } long long ans = min(A, B); cout << ans << "\n"; return 0; }
Идея проверена на примерах: для входа из условия программа выводит 7.