自动搬运

查看原文

来自洛谷，原作者为

	Ahws_rwhy 真実はいつもひとつ！ AH 目前在役Oier& 每日一%@dws_t7760

搬运于2025-08-24 23:01:34，当前版本为作者最后更新于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;
		}
	}
}