链接
题意
给你一个有向稀疏图，3000个点，5000条边。 问选出4个点A,B,C,D 使得 A-B, B-C, C-D 的最短路之和最大。
思路
枚举中间两个点，端点就是不与这三个点重复的最大的那个点来更新答案。因为是稀疏图，可以做n遍spfa来维护两两之间的最短路。
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <string>
#define LL long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define MAXN 3005
#define MAXM 5005
using namespace std;
struct Edge{
int to, next;
}edges[MAXM];
int head[MAXN];
int tot;
bool vis[MAXN];
int d[MAXN][MAXN];
int res[5];
vector<pair<int, int> > dis1[MAXN], dis2[MAXN];
void add_edge(int x, int y){
edges[tot].to = y;
edges[tot].next = head[x];
head[x] = tot++;
}
void spfa(int s){
queue<int> Q;
memset(vis, 0, sizeof(vis));
Q.push(s);
d[s][s] = 0;
while (!Q.empty()){
int x = Q.front(); Q.pop();
for (int i = head[x]; i != -1; i = edges[i].next){
int y = edges[i].to;
if (d[s][x] + 1 < d[s][y]){
d[s][y] = d[s][x] + 1;
}
if (vis[y]) continue;
vis[y] = true;
Q.push(y);
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
int n, m;
scanf("%d%d", &n, &m);
memset(head, -1, sizeof(head));
tot = 0;
int x, y;
for (int i = 1; i <= m; ++i){
scanf("%d%d", &x, &y);
add_edge(x, y);
}
memset(d, INF, sizeof(d));
for (int i = 1; i <= n; ++i){
spfa(i);
}
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= n; ++j){
if (d[i][j] != INF){
dis1[i].push_back(make_pair(d[i][j], j));
dis2[j].push_back(make_pair(d[i][j], i));
}
}
}
for (int i = 1; i <= n; ++i){
sort(dis1[i].rbegin(), dis1[i].rend());
sort(dis2[i].rbegin(), dis2[i].rend());
}
int ans = 0;
memset(res, 0, sizeof(res));
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= n; ++j){
if (i == j) continue;
if (d[i][j] == INF) continue;
for (int k = 0; k < min(3, (int)dis2[i].size()); ++k){
if (i == dis2[i][k].second || j == dis2[i][k].second) continue;
for (int l = 0; l < min(3, (int)dis1[j].size()); ++l){
if (j != dis1[j][l].second && i != dis1[j][l].second && dis2[i][k].second != dis1[j][l].second){
int temp = d[i][j] + dis2[i][k].first + dis1[j][l].first;
if (temp > ans){
ans = temp;
res[0] = dis2[i][k].second, res[1] = i, res[2] = j, res[3] = dis1[j][l].second;
}
}
}
}
}
}
//printf("%d
", ans);
for (int i = 0; i < 4; ++i){
printf("%d ", res[i]);
}
printf("
");
}