题解：P11350 [NOISG 2024 Finals] Shops

· · 题解

水一发题解。目前有的那一篇题解感觉写的完全没有道理。

考虑二分答案 w，则边权 \ge w 的边一定是没用的。对于剩下来的图，一个必要条件是：每个连通块的大小 \ge 2。

实际上，这个条件也是充分的。我们可以先删一些边使得每一个连通块都是二分图，然后二分图染色即可。这样构造的正确性显然。

根据上述分析，可以很容易的写出 check 和构造。复杂度 \mathcal{O}((n+m)\log V)，可能可以通过。

注意到我们只需要在 m 个边权里二分即可，复杂度 \mathcal{O}((n+m)\log m)，可以通过。

可能轻微卡常，这一点差评。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F(i, a, b) for (int i = (a); i <= (b); i ++ )
#define DF(i, a, b) for (int i = (a); i >= (b); i -- )
inline void chkmin(int& a, int b) { if (a > b) a = b; }
inline void chkmax(int& a, int b) { if (a < b) a = b; }

const int N = 500010, M = 2 * N, INF = 5e14;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int col[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int comp(int u, int lim)
{
    queue<int> q;
    int res = 0;
    q.push(u); st[u] = true;
    while (q.size())
    {
        int t = q.front(); q.pop();
        res ++ ;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (w[i] > lim || st[j]) continue;
            st[j] = true;
            q.push(j);
        }
    }
    return res;
}

bool check(int mid)
{
    F(i, 1, n) st[i] = 0;
    F(i, 1, n) if (st[i]) continue; else if (comp(i, mid) == 1) return false;
    return true;
}

void dfs(int u, int lim)
{
    st[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (w[i] > lim || st[j]) continue;
        col[j] = 3 - col[u];
        dfs(j, lim);
    }
}

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    vector<int> er;
    F(i, 0, m - 1)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
        er.push_back(c);
    }
    sort(er.begin(), er.end());
    int l = 0, r = (int)er.size() - 1, res = INF;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(er[mid])) r = mid - 1, res = er[mid];
        else l = mid + 1;
    }
    cout << res << "\n";
    F(i, 1, n) st[i] = 0;
    F(i, 1, n) if (!st[i]) col[i] = 1, dfs(i, res);
    F(i, 1, n) cout << (col[i] == 1 ? 'D' : 'B');
    cout << "\n";
    return 0;
}