CF666B World Tour

设最短路为 d ( x , y ) d(x,y) d(x,y),求四个点 a , b , c , d a,b,c,d a,b,c,d 最大化 d ( a , b ) + d ( b , c ) + d ( c , d ) d(a,b)+d(b,c)+d(c,d) d(a,b)+d(b,c)+d(c,d) 考虑枚举 b , c b,c b,c,如果能预处理出 m a x ( d ( a , x ) ) , m a x ( d ( x , d ) ) max(d(a,x) ),max(d(x,d)) max(d(a,x)),max(d(x,d))就好了. 然而 x x x可能与 b , c , d b,c,d b,c,d中的一个人重复,那么一个 x x x不行,就搞多几个 x x x. 处理出两个数组 f a r 1 ( x ) : 存前 3 个 d ( a , x ) 值最大的点 far1(x):存前3个d(a,x)值最大的点 far1(x):存前3个d(a,x)值最大的点 f a r 2 ( x ) : 存前 3 个 d ( x , a ) 值最大的点 far2(x):存前3个d(x,a)值最大的点 far2(x):存前3个d(x,a)值最大的点 那么在枚举 b , c b,c b,c的时候,再枚举 f a r 1 ( b ) , f a r 2 ( c ) far1(b),far2(c) far1(b),far2(c)就好了 最短路的处理由于边权可以看成1,用bfs处理出来,别用 d i j k s t r a , S P F A dijkstra,SPFA dijkstra,SPFA什么的

/*
I don't wanna be left behind,Distance was a friend of mine.
Catching breath in a web of lies,I've spent most of my life.
Catching my breath letting it go turning my cheek for the sake of this show
Now that you know this is my life I won't be told what's supposed to be right
Catch my breath no one can hold me back I ain't got time for that.
*/
#include
using namespace std;
const int maxn = 3000+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn],G1[maxn];//G1 是反图
vector far1[maxn],far2[maxn];//far1(x):要处理前3大个d(a,x)的点,
//far2(x):要处理d(x,a)大的点
int d1[maxn][maxn];//d1(i,j)shortest path in original graph
int d2[maxn][maxn];// ssp in reverse graph
bool vis[maxn];
void get_ssp1(int s){
	memset(vis,0,sizeof(vis));
	d1[s][s] = 0;vis[s] = true;
	queue q;q.push(s);
	while(!q.empty()){
		int u = q.front();q.pop();
		for(auto v : G[u]){
			if(vis[v]) continue;
			vis[v] = true;
			d1[s][v] = min(d1[s][v],d1[s][u]+1);
			q.push(v);
		}
	}
}
void get_ssp2(int s){
	memset(vis,0,sizeof(vis));
	d2[s][s] = 0;vis[s] = true;
	queue q;q.push(s);
	while(!q.empty()){
		int u = q.front();q.pop();
		for(auto v : G1[u]){
			if(vis[v]) continue;
			vis[v] = true;
			d2[s][v] = min(d2[s][v],d2[s][u]+1);
			q.push(v);
		}
	}
}
bool check(int &a,int &b,int &c,int &d){
	if(a==b||a==c||a==d) return false;
	if(b==c||b==d) return false;
	if(c==d) return false;
	return true;
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;cin>>n>>m;
	for(int i=1;i>u>>v;
		G[u].pb(v);G1[v].pb(u);
	}
	for(int i=1;i