【二分图染色】ARC 165 C

电玩女神 2024-03-01 00:46 33阅读 0赞

[C - Social Distance on Graph][]

题意：

![e3a90dac76b04c46b8c26e79ca5c9fee.png][]

思路：

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

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

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

在check时进行二分图染色

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

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    constexpr 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;
    }

[C - Social Distance on Graph]: https://atcoder.jp/contests/arc165/tasks/arc165_c
[e3a90dac76b04c46b8c26e79ca5c9fee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/64e485ea7bd548d5b890bdf472301b61.png