C - Social Distance on Graph

题意：

思路：

首先考虑一条链的情况，注意到如果两条相邻的边加起来 < x，一定不行

这个结论推广到图也是一样的

同时注意到 x 具有单调性，考虑对 x 二分

在check时进行二分图染色

不合法的情况是相邻的点相同颜色但是边权 < x

Code：

#include <bits/stdc++.h>#define int long longconstexpr int N = 2e5 + 10;
constexpr int M = 1e6 + 10;
constexpr int Inf = 1e9;std::vector<std::pair<int,int> > adj[N]; int n, m;
int mi1[N], mi2[N];
int col[N];bool dfs(int u, int c, int x) {col[u] = c;for (auto [v, w] : adj[u]) {if (col[v] == -1) {if (w < x) {if (!dfs(v, c ^ 1, x)) return false;}}else if (col[u] == col[v] && w < x) return false;}return true;
}
bool check(int mid) {memset(col, -1, sizeof(col));bool ok = true;for (int i = 1; i <= n; i ++) {if (col[i] == -1) {if (!dfs(i, 0, mid)) {ok = false;break;}}}return ok;
}
void solve() {std::cin >> n >> m;for (int i = 1; i <= n; i ++) {mi1[i] = mi2[i] = 1e18;}for (int i = 1; i <= m; i ++) {int u, v, w;std::cin >> u >> v >> w;adj[u].push_back({v, w});if (mi1[u] > w) {mi2[u] = mi1[u];mi1[u] = w;}else if (mi2[u] > w) {mi2[u] = w;}adj[v].push_back({u, w});if (mi1[v] > w) {mi2[v] = mi1[v];mi1[v] = w;}else if (mi2[v] > w) {mi2[v] = w;}}int r = 1e18;for (int i = 1; i <= n; i ++) {r = std::min(r, mi1[i] + mi2[i]);}int l = 0;int ans = 0;while (l <= r) {int mid = l + r >> 1;if (check(mid)) {ans = mid;l = mid + 1;}else {r = mid - 1;}}std::cout << ans << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while(t --) {solve();}return 0;
}