2020ICPC EC-Final D. City Brain

最编程 2024-02-26 08:31:52

...

题目链接
Prof. Pang works for the City Brain program of Capital Grancel. The road network of Grancel can be represented by an undirected graph. Initially, the speed limit on each road is $1$ m/s. Prof. Pang can increase the speed limit on a road by $1$ m/s with the cost of $1$ dollar. Prof. Pang has $k$ dollars. He can spend any nonnegative integral amount of money on each road. If the speed limit on some road is $a$ m/s, it takes $1 / a$ seconds for anyone to go through the road in either direction.

After Prof. Pang spent his money, Prof. Du starts to travel from city $s_1$ to city $t_1$ and Prof. Wo starts to travel from city $s_2$ to city $t_2$ . Help Prof. Pang to spend his money wisely to minimize the sum of minimum time of Prof. Du’s travel and Prof. Wo’s travel. It is guaranteed that $s_1$ and $t_1$ are connected by at least one path and that $s_2$ and $t_2$ are connected by at least one path.

Input

The first line contains three integers $n$ , $m$ , $k$ ( $1\le n \le 5000$ , $0\le m \le 5000$ , $0\le k\le 10^9$ ) separated by single spaces denoting the number of vertices, the number of edges in the graph and the number of dollars Prof. Pang has.

Each of the following $m$ lines contains two integers $a$ , $b$ ( $1\le a, b\le n, a\neq b$ ) separated by a single space denoting the two endpoints of one road. There can be multiple roads between the same pair of cities.

The following line contains four integers $s_1$ , $t_1$ , $s_2$ , $t_2$ ( $1\le s_1, t_1, s_2, t_2\le n$ ) separated by single spaces denoting the starting vertices and ending vertices of Prof. Du and Prof. Wo’s travels.

Output

Output one decimal in the only line – the minimum sum of Prof. Du’s travel time and Prof. Wo’s travel time. The answer will be considered correct if its absolute or relative error does not exceed $10^{-9}$ .

Examples

Input

Output

5.000000000000

显然根据贪心原则，要把修改次数用完。
对于长度为 $l$ 的路径，假设有 $x$ 次机会修改，则根据贪心原则，修改要尽可能平均，此时通过该路径的用时为 $\frac{x\mod l}{\left \lfloor \frac{x}{l} \right \rfloor+2}+\frac{l-(x\mod l)}{\left \lfloor \frac{x}{l} \right \rfloor+1}$ ,这个可以 $O (1)$ 计算。路径可以分为重复和不重复两部分，假设不重复部分分配 $x$ 次修改，则重复部分分配 $k - x$ 次修改。感性理解一下：由于重复部分和不重复部分用时关于 $x$ 的函数的导数均为减函数，因此总用时关于 $x$ 的函数为单峰函数或单调函数，利用三分可以 $O(\log k)$ 时间求出最值。
对于路径，首先可以观察到图为稀疏图且边权相等，因此可以通过枚举起点 bfs $O(n^2)$ 预处理出任意两点的最短路。之后 $O(n^2)$ 枚举重复路径的起点和终点得到重复路径和不重复路径长度，然而直接三分 $O(n^2\log k)$ 会超时，因此先筛掉相同重复路径长度中不重复路径长度较大的方案，然后枚举重复路径长度就可以将复杂度降为 $O(n\log k)$ 。
最终时间复杂度为 $O(n^2+n\log k)$ 。

#include <bits/stdc++.h>

#define get(l, x) ((l) ? (double((x) % (l)) / double((x) / (l) + 2) + double((l) - (x) % (l)) / double((x) / (l) + 1)) : 0)
#define f(l1, l2, x) (get(l1, x) + 2 * get(l2, k - (x)))
using namespace std;
const int N = 5005, INF = 0x3f3f3f3f;
int head[N], ver[N << 1], Next[N << 1], tot;
int n, m, k, s1, t1, s2, t2, d[N][N], mn[N];
queue<int> q;

inline void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}

inline void bfs(int s) {
    memset(d[s] + 1, 0x3f, sizeof(int) * n);
    q.push(s), d[s][s] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = Next[i]) {
            if (d[s][ver[i]] != INF) continue;
            d[s][ver[i]] = d[s][x] + 1, q.push(ver[i]);
        }
    }
}

inline double calc(int l1, int l2) {
    if (!l1 && !l2) return 0;
    if (!l2) return get(l1, k);
    if (!l1) return 2 * get(l2, k);
    int l = 0, r = k, lmid, rmid, ans;
    while (l <= r) {
        lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
        f(l1, l2, lmid) >= f(l1, l2, rmid) ? (l = lmid + 1, ans = rmid) : (r = rmid - 1);
    }
    return f(l1, l2, ans);
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    for (int i = 1; i <= n; i++) bfs(i);
    scanf("%d%d%d%d", &s1, &t1, &s2, &t2);
    memset(mn + 1, 0x3f, sizeof(int) * n);
    mn[0] = d[s1][t1] + d[s2
						
							上一篇：							
								BCI比赛数据集简介-BCI competition IV 2b							
						
						
							下一篇：							
								标题：关于JetBrains的登录失败问题 JetBrains Account connection error-摘要


															
						
							推荐阅读						
						
														
								
									
										2020ICPC EC-Final D. City Brain