题解：P10819 [EC Final 2020] City Brain

· · 题解

题意

link

思路

对本题目标函数观察 / 求导后易得目标函数单峰，可得三分思路。

又由本题均摊花费的 trick，可以确定“均摊花费到每条边上”的贪心策略。

于是本题就结束了。

本题弱化版（宜强化 trick）：P14318。

Code

::::warning[本题解 Code 由 ChatGPT-5 润色，折叠框内为 Code]{open}

AC Link

#include <bits/stdc++.h>
using namespace std;
using db = double;

const int N = 5010;
const int INF = 0x3f3f3f3f;

int n, m, k;
vector<int> E[N];
int dis[N][N];
bool vis[N];
queue<int> q;

int s1, t1, s2, t2;

void bfs(int stu) {
    memset(vis, 0, sizeof vis);
    while (!q.empty()) q.pop();
    vis[stu] = 1;
    dis[stu][stu] = 0;
    q.push(stu);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : E[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                dis[stu][v] = dis[stu][u] + 1;
                q.push(v);
            }
        }
    }
}

inline db cg(int l, int x) {
    if (!l) return 0;
    int a = x / l, b = x % l;
    return (db) b / (a + 2) + (db) (l - b) / (a + 1);
}

inline db ch(int l1, int l2, int x) {
    return cg(l1, x) + 2.0 * cg(l2, k - x);
}

inline db cr(int l1, int l2) {
    if (!l1 && !l2) return 0;
    if (!l2) return cg(l1, k);
    if (!l1) return 2.0 * cg(l2, k);
    int L = 0, R = k, ans = 0;
    while (L <= R) {
        int m1 = L + (R - L) / 3;
        int m2 = R - (R - L) / 3;
        if (ch(l1, l2, m1) >= ch(l1, l2, m2))
            L = m1 + 1, ans = m2;
        else
            R = m2 - 1;
    }
    return ch(l1, l2, ans);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> k;
    for (int i = 1, u, v; i <= m; ++i) {
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    memset(dis, 0x3f, sizeof dis);
    for (int i = 1; i <= n; ++i) bfs(i);
    cin >> s1 >> t1 >> s2 >> t2;
    static int mn[N];
    memset(mn, 0x3f, sizeof mn);
    mn[0] = dis[s1][t1] + dis[s2][t2];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            if (dis[i][j] == INF) continue;
            if (dis[s1][i] == INF || dis[s2][i] == INF) continue;
            if (dis[j][t1] == INF || dis[j][t2] == INF) continue;
            int pub = dis[i][j];
            int rest =
                min(dis[s1][i] + dis[j][t1], dis[s1][j] + dis[i][t1]) +
                min(dis[s2][i] + dis[j][t2], dis[s2][j] + dis[i][t2]);
            mn[pub] = min(mn[pub], rest);
        }
    db ans = 1e18;
    for (int i = 0; i <= n; ++i)
        if (mn[i] != INF)
            ans = min(ans, cr(mn[i], i));
    cout << fixed << setprecision(15) << ans << "\n";
}

::::