TIOJ 2125：殿壬與情人節

TIOJ 2125：殿壬與情人節

題目大意：有一棵 $n$ 點的樹，有 $m$ 個藍點與 $m$ 個紅點，有 $m$ 個守衛，一個守衛掌管一個藍點與紅點，可挑選一點當休息室，要從休息室出發巡邏完兩點後回到休息室，需要花費電力照亮手電筒，每走一單位距離即用到一單位電力，回到休息室可將電力充到電容量。每個守衛的手電筒都有相同的電容量，問在適當的休息室及藍點紅點分配下，電容量最低可以是多少。

解法：首先看只有一藍點與紅點下的電容量：可以找他們的 $LCA$，分別二分搜藍點到休息室，紅點到休息室的兩段距離最大值最小可以是多少。之後我們算出來每種不同配對狀況的電容量。之後對電容量二分搜，如果 $Dis[i][j]$ 小於等於電容量，就可以連一條 $i,j$ 的邊，做二分圖最大匹配看能不能湊成 $m$ 對。最後即可得到答案。

ps. 這題是我用 rand(1001,2242) 找到的，然後明天都要初選了我還在寫 Blog...

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define Waimai ios::sync_with_stdio(false)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 5e5 + 5;
const int MSIZ = 305;
const int H = __lg (SIZE) + 1;
const int INF = 1e15;

int n, m;
vector<pair<int, int>> adj[SIZE];
int h[SIZE], to[SIZE][H + 1], len[SIZE][H + 1];
int p1[MSIZ], p2[MSIZ], match[MSIZ], Dis[MSIZ][MSIZ];
vector<int> madj[MSIZ];
bool vs[MSIZ];

void dfs (int pos, int fa) {
    for (auto [np, w] : adj[pos]) {
        if (np != fa) {
            h[np] = h[pos] + 1;
            to[np][0] = pos;
            len[np][0] = w;
            dfs (np, pos);
        }
    }
}

int jump (int pos, int k, int &ans) {int cnt = 0; while (k) {if (k & 1) {ans += len[pos][cnt]; pos = to[pos][cnt];} cnt++; k >>= 1;} return pos;}
int lca (int a, int b, int &ans) {
    if (h[a] < h[b]) {
        swap (a, b);
    }
    a = jump (a, h[a] - h[b], ans);
    if (a == b) {
        return a;
    }
    for (int i = H; i >= 0; i--) {
        if (to[a][i] != to[b][i]) {
            ans += len[a][i] + len[b][i];
            a = to[a][i];
            b = to[b][i];
        }
    }
    ans += len[a][0] + len[b][0];
    return to[a][0];
}

int cal (int a, int b) {
    int _, root = lca (a, b, _), l, r, adis = 0, bdis = 0, re = INF;
    jump (a, h[a] - h[root], adis);
    jump (b, h[b] - h[root], bdis);
    l = 0, r = h[a] - h[root];
    while (l < r) {
        int mid = (l + r) / 2, ldis = 0, rdis = bdis, d1, d2, t;
        t = jump (a, mid, ldis);
        rdis += adis - ldis;
        d1 = max (ldis, rdis);
        ldis += len[t][0];
        rdis -= len[t][0];
        d2 = max (ldis, rdis);
        if (d1 < d2) {
            r = mid;
            re = min (re, d1);
        } else {
            l = mid + 1;
            re = min (re, d2);
        }
    }
    l = 0, r = h[b] - h[root];
    while (l < r) {
        int mid = (l + r) / 2, ldis = 0, rdis = adis, d1, d2, t;
        t = jump (b, mid, ldis);
        rdis += bdis - ldis;
        d1 = max (ldis, rdis);
        ldis += len[t][0];
        rdis -= len[t][0];
        d2 = max (ldis, rdis);
        if (d1 < d2) {
            r = mid;
            re = min (re, d1);
        } else {
            l = mid + 1;
            re = min (re, d2);
        }
    }
    return re;
}

bool bimatch (int pos) {
    for (int np : madj[pos]) {
        if (!vs[np]) {
            vs[np] = 1;
            if (match[np] == 0 || bimatch (match[np])) {
                match[np] = pos;
                return 1;
            }
        }
    }
    return 0;
}

bool ok (int x) {
    fill (madj, madj + m + 1, vector<int>());
    fill (match, match + m + 1, 0);
    FOR (i, 1, m) FOR (j, 1, m) {
        if (Dis[i][j] <= x) {
            madj[i].pb (j);
        }
    }
    int cnt = 0;
    FOR (i, 1, m) {
        fill (vs, vs + m + 1, 0);
        cnt += bimatch (i);
    }
    return cnt == m;
}

void solve() {
    cin >> n >> m;
    FOR (i, 2, n) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].pb (b, w);
        adj[b].pb (a, w);
    }
    dfs (1, 1);
    FOR (i, 1, H) FOR (j, 1, n) {
        int fa = to[j][i - 1];
        to[j][i] = to[fa][i - 1];
        len[j][i] = len[j][i - 1] + len[fa][i - 1];
    }
    FOR (i, 1, m) cin >> p1[i];
    FOR (i, 1, m) cin >> p2[i];
    FOR (i, 1, m) FOR (j, 1, m) {
        int a = p1[i], b = p2[j];
        Dis[i][j] = 2 * cal (a, b);
    }
    int l = 0, r = INF;
    while (l < r) {
        int mid = (l + r) / 2;
        if (ok (mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << l << '\n';
}

int32_t main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！