bfs+双向搜索的思路

时间复杂度O(n^2)

主要思路是建出一张新图f：f[i][j]=1表示点i和点j在K步之内可达。

然后在图f上跑搜索，记录所有的从点1开始2步（新图上的2步）之内可以到达的点以及相关信息。复杂度O(n^2)

然后O(n^2)合并这些信息，输出答案。

双向搜索需要维护一个数组g，定义g如下：

pair<int,vector> g[2505][3][3]

其中g[i][j][k]表示以点i为末尾的一条1->i的链，链长为g（长度不包括链头1），这一条链的点权和是已知的最大值/次大值/次次大值(k=0/1/2)。

其中g[i][j][k].first存储的是点权和，g[i][j][k].second存储的是目前链上已有的点。

然后是合并的部分，枚举点i、j作为一个长度为2（不包括链头）的链的末尾，如果i、j在图f上连通，那么更新答案： 题目要求不能有重复的点，那么如果有重复的点那么答案就不合法，不能加入答案，更新答案要使用最大的合法答案。

注意到一个链上只有两个点，且保证i!=j，那么最大值/次大值/次次大值中至少有一个合法答案，分别枚举一下，更新答案即可。

注意到双向搜索复杂度大致是O(n^2×9log3)，合并复杂度大致是O(n^2×9)，大概是，我没仔细算。

没有看题解，时间复杂度应该是对的，自我感觉应该卡卡常能过！求大佬卡常！

#include<iostream>
#include<algorithm>
#include<queue>
#include<array>
#include<cstring>
#include<vector>
using namespace std;
#define int long long
vector<vector<int>> a;
int n,m,K;
int h[2505];
bool vis[2505];
bool f[2505][2505];
typedef pair<int,pair<int,int>> edge;
void bfs(int x) {
	vis[x]=true;
	queue<pair<int,int>> q;
	q.push(pair<int,int> {x,0});
	while(!q.empty()) {
		int u=q.front().first;
		int step=q.front().second;
		q.pop();
		f[x][u]=f[u][x]=1;
		if(step==K+1) continue;
		for(auto&v:a[u]) {
			if(vis[v]) continue;
			q.push(pair<int,int> {v,step+1});
			vis[v]=true;
		}
	}
}
int maxx;
pair<int,vector<int>> g[2505][3][3];
//g[i][j][k]，表示第i个节点，目前长度为1/2，维护的是最大值/次大值/次次大值
int push(pair<int,vector<int>> x[3],pair<int,vector<int>> y) {
	vector<pair<int,vector<int>>> v;
	for(int i=0; i<3; i++)
		v.push_back(x[i]);
	v.push_back(y);
	sort(v.begin(),v.end(),greater<pair<int,vector<int>>>());
	int t=0;
	while(t<v.size()&&v[t]!=y)
		t++;
	if(t==v.size())	return -1;
//	cout<<"sort:";
	for(int i=0; i<3; i++)
		x[i]=v[i]
//		,cout<<v[i].first<<' '
		     ;
//	cout<<endl;
	return t;
}
void dfs(int u,int step,pair<int,vector<int>> w) {
	if(step==2) return ;
	for(int v=1; v<=n; v++) {
		if(f[u][v]&&u!=v&&!vis[v]) {
			auto x=w.second;
			x.push_back(v);
			int t=push(g[v][step+1],pair<int,vector<int>> {w.first+h[v],x});
//			if(~t)
//				cout<<t<<"("<<v<<','<<step+1<<")""->"<<g[v][step+1][t].first<<endl;
			vis[v]=true;
			if(~t)
				dfs(v,step+1,g[v][step+1][t]);
			vis[v]=false;
		}
	}
}
bool have_eq(vector<int>x,vector<int>y) {
	for(auto&i:x)
		for(auto&j:y)
			if(i==j)
				return true;
	return false;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>K;
	for(int i=0; i<=n; i++)
		a.push_back(vector<int> {});
	for(int i=2;i<=n; i++)
		cin>>h[i];
	for(int i=1; i<=m; i++) {
		int u,v;
		cin>>u>>v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for(int i=1; i<=n; i++) {
		bfs(i);
		memset(vis,0,sizeof vis);
	}
//	for(int i=1; i<=n; i++,cout<<endl)
//		for(int j=1; j<=n; j++)
//			cout<<f[i][j]<<' ';
	vis[1]=true;
	dfs(1,0,g[0][0][0]);
	vis[1]=false;
//	for(int i=1; i<=n; i++) {
//		cout<<i<<':'<<endl;
//		for(int k=0; k<3; k++) {
//			cout<<"maxx"<<k<<':'<<g[i][2][k].first;
//			for(auto&j:g[i][2][k].second)
//				cout<<' '<<j;
//			cout<<endl;
//		}
//	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			if(f[i][j])
				for(int x=0;x<3&&g[i][2][x].first;x++)
					for(int y=0;y<3&&g[j][2][y].first;y++)
						if(!have_eq(g[i][2][x].second,g[j][2][y].second))
							maxx=max(maxx,g[i][2][x].first+g[j][2][y].first);
	cout<<maxx;
	return 0;
}