「NOIP2007」树网的核

传送门

Luogu

解题思路

这里着重介绍 \(O(n^3)\) 的做法，毕竟考场上只有 \(N\le300\) \(Q \omega Q\)

首先我们要知道，对任意一条直径算偏心距都是一样的。

证明

首先任意两条直径都必定会相交，否则把这两条直径相连就会得到更长的路径来充当直径。

其次相交的直径在不相交的部分，长度分别相等，不然就不能保证两者都是等长的直径。

然后我们肯定要知道，一条偏心距一定是一个点到直径端点的距离，不然保证不了最长。

如果偏心距包含了一些直径的交，那么这些偏心距一定都是等长的，可以根据上面的推论证明；如果不包含，就一定不会比包含的优，所以只要跨过公共部分就可以了，也就是说任意一条都可以。

所以先 \(O(n^3)\) \(\text{Floyd}\) 求出树的一条直径。

然后 \(O(n^2)\) 暴力枚举一条直径上的长度不超过 \(s\) 的路径，在枚举一个点 \(k\) 计算当前的偏心距，最后把所有偏心距取 \(\min\) 。

然后提一下两个事情：

\(d[i][x]+d[x][j]=d[i][j]\) 说明 \(x\) 在路径 \((i, j)\) 上；

\((d[i][x] + d[j][x] - d[i][j])/2\) 表示 \(x\) 和 \((i, j)\) 的距离。

证明很简单，画个图就好了。

细节注意事项

咕咕咕

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= c == '-', c = getchar();

	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

	s = f ? -s : s;

}

const int _ = 302;

int n, s, d[_][_];

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	read(n), read(s);

	memset(d, 0x3f, sizeof d);

	for (rg int i = 1; i <= n; ++i) d[i][i] = 0;

	for (rg int u, v, x, i = 1; i < n; ++i)

		read(u), read(v), read(x), d[u][v] = d[v][u] = min(d[u][v], x);

	for (rg int k = 1; k <= n; ++k)

		for (rg int i = 1; i <= n; ++i)

			for (rg int j = 1; j <= n; ++j)

				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

	int tp = 0, bt = 0, D = 0;

	for (rg int i = 1; i <= n; ++i)

		for (rg int j = 1; j <= n; ++j)

			if (D < d[i][j])

				D = d[i][j], tp = i, bt = j;

	int ans = 2147483647;

	for (rg int i = 1; i <= n; ++i) {

		if (d[tp][i] + d[i][bt] != D) continue;

		for (rg int j = 1; j <= n; ++j) {

			if (d[tp][j] + d[j][bt] != D) continue;

			if (d[i][j] > s) continue;

			int ecc = -1;

			for (rg int k = 1; k <= n; ++k)

				ecc = max(ecc, (d[i][k] + d[j][k] - d[i][j]) >> 1);

			ans = min(ans, ecc);

		}

	}

	printf("%d\n", ans);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「NOIP2007」树网的核

解题思路

细节注意事项

参考代码

最新文章

热门文章