Codeforces Round 349 B World Tour(最短路 + 枚举)

题目大意

给定一个 $N$ 个点,$M$ 条边的有向图。现将选择 $4$ 个不同的点进行顺序访问(从第 $1$ 个点出发,在第 $4$ 个点结束),并满足点与点之间的最短路距离之和最大。输出符合条件的任意 $4$ 个点。注意可多次经过同一个点。
$(4 \le n \le 3000, 3 \le m \le 5000)$

解题思路

最短路+枚举

先跑最短路,计算 $f(u,v)$ 表示 $u$ 到 $v$ 的最短路。

对于所求问题 $a \to b \to c \to d$,枚举 $b$ 和 $c$,之后枚举 $f(a,b)$ 中最大的 $3$ 个 $a$,和 $f(c,d)$ 中最大的 $3$ 个 $d$(跑最短路时可以预处理出 $3$ 个最大的点),check一下就可以了。

为什么只需要枚举最大的 $3$ 个点就可以呢?考虑对 $f(a,b)$ 中 $a$ 的枚举,由于 $a \notin {b, c, d}$,所以 $a$ 的不合法取值只有 $3$ 个,且预处理时可以保证 $a \ne b$,所以 $a$ 可能的取值只有 $f(x,b)$ 中最大的 $3$ 个 $x$。枚举 $d$ 同理。

官方题解:

You are given the oriented graph, find four distinct vertices a, b, c, d such that each vertex if reachable from previous and the sum of shortest paths between consequitive vertices is as large as possible. First let’s run a BFS from each vertex and find three most distant vertices over given graph and its reverse. Afterwards loop through each possible b and c. Having them fixed, loop through a among three most distant vertices from b in the reversed graph and through d among three most distant vertices from c in tie initial graph. This is sufficient, because if we’ve fixed b and c and d is not one of three furthest from c then we could replace it with one of them and improve the answer.

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int MAXN = 3e3 + 10;
const int MAXM = 5e3 + 10;

int n, m;
int dist[MAXN][MAXN];
vector<int> G[MAXN];
vector<P> maze[MAXN], rmaze[MAXN];

void bfs(int s)
{

memset(dist[s], -1, sizeof(dist[s]));
queue<int> que;
que.push(s);
dist[s][s] = 0;
while( !que.empty() ) {
int u = que.front(); que.pop();
for( int i = 0; i < G[u].size(); ++ i ) {
int v = G[u][i];
if( dist[s][v] == -1 ) {
dist[s][v] = dist[s][u] + 1;
que.push(v);
}
}
}
}
int main()
{

while( ~scanf("%d %d", &n, &m) ) {
int u, v;
for( int i = 0; i < m; ++ i ) {
scanf("%d %d", &u, &v);
G[u].push_back(v);
}
for( int i = 1; i <= n; ++ i ) bfs(i);
for( int i = 1; i <= n; ++ i ) {
for( int j = 1; j <= n; ++ j ) {
if( i == j || dist[i][j] == -1 ) continue;
maze[i].push_back(P(dist[i][j], j));
rmaze[j].push_back(P(dist[i][j], i));
}
sort(maze[i].begin(), maze[i].end(), greater<P>());
if( maze[i].size() > 3 ) maze[i].resize(3);
}
for( int i = 1; i <= n; ++ i ) {
sort(rmaze[i].begin(), rmaze[i].end(), greater<P>());
if( rmaze[i].size() > 3 ) rmaze[i].resize(3);
}
int A, B, C, D, Max = 0;
for( int b = 1; b <= n; ++ b ) {
for( int c = 1; c <= n; ++ c ) {
if( b == c || dist[b][c] == -1 ) continue;
for( int i = 0; i < rmaze[b].size(); ++ i ) {
int a = rmaze[b][i].second;
if( a == c ) continue;
for( int j = 0; j < maze[c].size(); ++ j ) {
int sum = dist[a][b] + dist[b][c];
int d = maze[c][j].second;
if( a == d || b == d ) continue;
sum += dist[c][d];
if( sum > Max ) {
Max = sum;
A = a, B = b, C = c, D = d;
}
}
}
}
}
printf("%d %d %d %d\n", A, B, C, D);
}
return 0;
}
如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!