题解：P10819 [EC Final 2020] City Brain

Ahws_rwhy · 2024-08-04 21:32:42 · 题解

哇，写了 1 个小时，一百多行代码，总算过了。

思路：

对于两条路径，一定是中间有重合的一段，而不是有两段，否则，对于两个人中间分开的那一段路径一定可以选择一条更短的路走，从而将两段重合路径合并成了一段。

可以枚举重合的路径的两个端点，那么重合的路径长度以及不重合的路径的长度就可以确定了，假设重复端点为 N，那么预处理一下重叠部分为 N 的时候其他路径的最短和 s_1，这个 \mathcal O(n ^ 2) 可以处理出来，我们发现我们不好确认分给重叠部分的次数多少，于是，三分给重叠部分的操作次数；之后，处理一下，问题又变成了给长度为 m 的路径分配 x 次操作的最小代价，这个还是比较容易考虑的，首先就是均分次数，多余的，也是均分。

接着处理一些细节即可。

double solve(int b, int a) {
    if (a > inff || b > inff) return inff;
    if (a == 0 && b == 0) return 0;
    int k = tempk;
    int v = (k + a + b) / (genhao2 * a + b) ;
    int u = genhao2 * v;
    if (u > 1) u--;
    if (v > 1) v--;
    if (u < 1) u = 1;
    if (v < 1) v = 1;
//  cout << u << " " << v << endl;
    k -= a * (u - 1) + b * (v - 1);
    ans = a * (2.0 / u) + b * (1.0 / v);
//  cout << ans << endl;
    while (k != 0) {
        if (1 * u * (u + 1) < 2 * v * (v + 1)) {
            int time = min(k, a);
            ans -= time * (2.0 / (u * (u + 1)));
            k -= time;
            u++;
        } else {
            int time = min(k, b);
            ans -= time * (1.0 / (v * (v + 1)));
            k -= time;
            v++;
        }
    }
    return ans;
}
void add(int u, int v) {
    to[++sum] = v ;
    next_side[sum] = first_side[u] ;
    first_side[u] = sum;
}
void bfs(int step, int dis[]) {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) dis[i] = inff;
    queue <int> Q;
    vis[step] = 1;
    Q.push(step);
    dis[step] = 0;
    while (!Q.empty()) {
        int front_ = Q.front();
        Q.pop();
        for (int i = first_side[front_]; i != 0; i = next_side[i]) {
            int to_ = to[i];
            if (vis[to_]) continue;
            Q.push(to_);
            vis[to_] = 1;
            dis[to_] = dis[front_] + 1;
        }
    }
}