题解：P14318 「ALFR Round 11」B 行走 (walk)

首先判掉小 A 或小 B 走无法到达目标地点的情况。

显然，小 A 和小 B 走到目标地点的边数一定可以最小化，否则一定可以造出相对应的边数最小的不更劣的方案。

然后这个题就变成了一道数学题。

记小 A 和小 B 走到目标地点的边数为总和的最小值为

n

。

那么这道题相当于给定

x_1 + x_2 + \ldots + x_n = k

，求

\displaystyle (\sum_{i = 1}^n \frac{1}{1 + x_i})_{\displaystyle \min}

。

考虑到如果有还可以更接近的两项及即

x_i - x_j \ge 2

，则

\displaystyle \frac{1}{1 + x_i} + \frac{1}{1 + x_j} > \frac{1}{1 + (x_i - 1)} + \frac{1}{1 + (x_j + 1)}

（读者自证）。

所以可以得到一定是

x

中的数一定是

t, \ldots, t, t + 1, \ldots, t + 1

（可以没有

t + 1

）。

\large{\mathbf{Code}}

CPP

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int T, n, m, s, t, x, y, dist[N];
ll k;
vector<int> g[N];
queue<int> q;
int get(int s, int t) {
	memset(dist, -1, sizeof dist);
	dist[s] = 0;
	q.push(s);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int v : g[u])
			if(!~dist[v]) {
				dist[v] = dist[u] + 1;
				q.push(v);
			}
	}
	return dist[t];
}
int main()
{
	scanf("%d", &T);
	while(T --) {
		scanf("%d%d%lld", &n, &m, &k);
		for(int i = 1; i <= n; i ++) g[i].clear();
		while(m --) {
			scanf("%d%d", &x, &y);
			g[x].push_back(y), g[y].push_back(x);
		}
		scanf("%d%d%d%d", &s, &t, &x, &y);
		int a = get(s, t), b = get(x, y);
		if(!~a || !~b) {
			puts("-1");
			continue;
		}
		int v = a + b;
		if(!v) { // 注意特判这里
			puts("0");
			continue;
		}
		int lef = k % v;
		printf("%.12lf\n", lef * 1.0 / (k / v + 2) + (v - lef) * 1.0 / (k / v + 1));
	}
	return 0;
}

题解：P14318 「ALFR Round 11」B 行走 (walk)

文章操作

相关推荐

评论

题解：P14318 「ALFR Round 11」B 行走 (walk)