CF666B. World Tour

题意：

给定一张边权为 1 的有向图，求四个不同点 A, B, C, D

使得 dis(A, B) + dis(B, C) + dis(C, D) 取最大值，dis表示最短路距离 1 ≤ n ≤ 3000, 1 ≤ m ≤ 5000

---

我又写了假做法呜呜呜

首先当然\(O(nm)\)预处理两点之间最短路

然后预处理出从每个点开始前3个dis最大的点

假做法：

贪心，枚举A，贪心选择dis较大的BCD，就是3*3*3搜索选出B、C、D

假的原因：

贪心不成立，因为前面会影响后面，可以先差，再优、优

真做法：

再预处理到达每个点的前3个dis最大的点

枚举B、C，再3*3选出A、D，选A、D不会像之前那样互相干扰了

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int N = 1e4+5, inf = 1e9;

int n, m;

struct edge {int v, ne;} e[N];

int cnt, h[N], d[N][N];

inline void ins(int u, int v) {

	e[++cnt] = (edge) {v, h[u]}; h[u] = cnt;

}

int q[N], head, tail, vis[N];

#define fir first

#define sec second

pair<int, int> a[N], f[N][5], g[N][5];

void bfs(int s) {

	memset(vis, 0, sizeof(vis));

	head = tail = 1;

	q[tail++] = s; vis[s] = 1;

	memset(d[s], 0x3f, sizeof(d[s]));

	int *dis = d[s];

	dis[s] = 0;

	while(head != tail) {

		int u = q[head++];

		for(int i=h[u]; i; i=e[i].ne) {

			int v = e[i].v;

			if(vis[v]) continue;

			dis[v] = dis[u] + 1;

			vis[v] = 1;

			q[tail++] = v;

		}

	}

}

void solve(int s) {

	int cnt = 0;

	for(int i=1; i<=n; i++) if(i!=s && d[s][i] < inf) a[++cnt] = make_pair(d[s][i], i);

	for(int i=cnt+1; i<=3; i++) a[i] = make_pair(0, 0);

	sort(a+1, a+cnt+1, greater<pair<int, int> >());

	f[s][1] = a[1], f[s][2] = a[2], f[s][3] = a[3];

	cnt = 0;

	for(int i=1; i<=n; i++) if(i!=s && d[i][s] < inf) a[++cnt] = make_pair(d[i][s], i);

	for(int i=cnt+1; i<=3; i++) a[i] = make_pair(0, 0);

	sort(a+1, a+cnt+1, greater<pair<int, int> >());

	g[s][1] = a[1], g[s][2] = a[2], g[s][3] = a[3];

	//if(s == 1) printf("hi %d %d %d\n", a[1].sec, a[2].sec, a[3].sec);

	//printf("sssssssssssssssssssssssssssss %d\n", s);

	//for(int i=1; i<=3; i++) printf("f %d   %d %d\n", i, f[s][i].fir, f[s][i].sec);

}

int ans, li[10];

int main() {

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

	ios::sync_with_stdio(false); cin.tie(); cout.tie();

	cin >> n >> m;

	for(int i=1; i<=m; i++) {

		int u, v;

		cin >> u >> v;

		if(u != v && !d[u][v]) ins(u, v), d[u][v] = 1;

	}

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

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

	for(int b=1; b<=n; b++)

		for(int c=1; c<=n; c++) if(d[b][c] < inf && c != b) {

			int now = d[b][c];

			for(int i=1; i<=3; i++) {

				pair<int, int> &ra = g[b][i];

				int a = ra.sec;

				if(a == b || a == c || !ra.fir) continue;

				now += ra.fir;

				for(int j=1; j<=3; j++) {

					pair<int, int> &rd = f[c][j];

					int d = rd.sec;

					if(d ==a || d == b || d == c || !rd.fir) continue;

					now += rd.fir;

					if(now > ans) {

						ans = now;

						li[1] = a; li[2] = b; li[3] = c; li[4] = d;

					}

					now -= rd.fir;

				}

				now -= ra.fir;

			}

		}

	for(int i=1; i<=4; i++) cout << li[i] << ' ';

}