P8817 假期计划 Sol

看到数据范围，很容易想到平方。

由于是双向边，所以很容易想到其实四个点可以被拆成两部分，两部分本质一样，可以一起处理。

考虑枚举中转点 \(x,y\)，可以想到预处理与 \(x\) 距离不超过 \(k+1\)、且与 \(1\) 距离不超过 \(k+1\) 的点，同理有 \(y\)。

想到与 \(x\) 相连的点可能为 \(1,y,\) 与 \(y\) 相连的满足条件的点，所以保险起见预处理点权前 \(4\) 大。

没了。

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define pli pair <ll, int>
using namespace std;

const int N = 2.5e3 + 10, INF = 1e9;
int n, m, k, num[N][20], len[N], dis[N][N];
ll res, vl[N], val[N][N]; bool vis[N]; vector <int> g[N];
priority_queue <pii, vector <pii>, greater <pii> > q;
set <pair <ll, int> > S[N];

inline void dij(int st) {
	for (int i = 1; i <= n; ++i) dis[st][i] = INF; dis[st][st] = 0;
	for (int i = 1; i <= n; ++i) vis[i] = false;
	while (!q.empty()) q.pop(); q.push(make_pair(0, st));
	while (!q.empty()) {
		int cur = q.top().second; q.pop();
		if (vis[cur]) continue; vis[cur] = true;
		for (int i = 0; i < g[cur].size(); ++i) {
			int to = g[cur][i];
			if (dis[st][to] > dis[st][cur] + 1) {
				dis[st][to] = dis[st][cur] + 1;
				q.push(make_pair(dis[st][to], to));
			}
		}
	}
	return ;
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 2; i <= n; ++i) scanf("%lld", &vl[i]);
	for (int i = 1, u, v; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		g[u].push_back(v), g[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i) dij(i);
  for (int i = 2; i <= n; ++i) {
  	for (int j = 2; j <= n; ++j) {
  		if (i == j || (dis[j][i] > k + 1) || (dis[1][j] > k + 1)) continue;
  		S[i].insert(make_pair(vl[j], j)); if (S[i].size() > 5) S[i].erase(S[i].begin());
		}
	}
	for (int i = 2; i <= n; ++i) {
		set <pli>::iterator it;
		for (it = S[i].begin(); it != S[i].end(); ++it)
		  num[i][++len[i]] = (*it).second;
	}
	for (int se = 2; se <= n; ++se)
		for (int th = 2; th <= n; ++th) {
			if (se == th || dis[se][th] > k + 1) continue;
      if ((!len[se]) || (!len[th])) continue;
      for (int i = 1; i <= len[se]; ++i)
        for (int j = 1; j <= len[th]; ++j) {
        	if (num[se][i] == th || num[th][j] == se || num[se][i] == num[th][j]) continue;
        	res = max(res, vl[se] + vl[th] + vl[num[se][i]] + vl[num[th][j]]);
//        	if (res == 3954) cout << lef[i] << ' ' << se << ' ' << th << ' ' << rig[i] << endl;
				}
		}
	printf("%lld\n", res);
	return 0;
}

原文地址：http://www.cnblogs.com/MistZero/p/P8817-Sol.html