记录编号 577291 评测结果 AAAAAAWWWWWAAAAWWWWA
题目名称 [CSP 2022S]假期计划 最终得分 55
用户昵称 Gravatarnick 是否通过 未通过
代码语言 C++ 运行时间 6.072 s
提交时间 2022-10-30 13:19:02 内存使用 41.13 MiB
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> v[5000];
queue<ll> p;
ll n,m,k,a[5000],ans,dl[3000][3000],e[5000],b1[3000],b2[3000],b3[3000];
void dfs(ll x,ll r,ll l)
{
	if(r==3)
	{
		if(a[l]>a[b1[x]])
		{
			b3[x]=b2[x];
			b2[x]=b1[x];
			b1[x]=l;
		}
		else
		{
			if(a[l]>a[b2[x]])
			{
				b3[x]=b2[x];
				b2[x]=l;
			}
			else if(a[l]>a[b3[x]]) b3[x]=l;
		}
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(e[i]==0&&dl[x][i]<=k+1)
		{
			e[i]=1;
			dfs(i,r+1,x);
			e[i]=0;
		}
	}
}
void dou1(int i,int j)
{
	if(b1[j]!=i&&b1[j]!=b1[i]&&b1[j])ans=max(ans,a[i]+a[j]+a[b1[i]]+a[b1[j]]);
	if(b2[j]!=i&&b2[j]!=b1[i]&&b2[j])ans=max(ans,a[i]+a[j]+a[b1[i]]+a[b2[j]]);
	if(b3[j]!=i&&b3[j]!=b1[i]&&b3[j])ans=max(ans,a[i]+a[j]+a[b1[i]]+a[b3[j]]);
}
void dou2(int i,int j)
{
	if(b1[j]!=i&&b1[j]!=b2[i]&&b1[j])ans=max(ans,a[i]+a[j]+a[b2[i]]+a[b1[j]]);
	if(b2[j]!=i&&b2[j]!=b2[i]&&b2[j])ans=max(ans,a[i]+a[j]+a[b2[i]]+a[b2[j]]);
	if(b3[j]!=i&&b3[j]!=b2[i]&&b3[j])ans=max(ans,a[i]+a[j]+a[b2[i]]+a[b3[j]]);
}
void dou3(int i,int j)
{
	if(b1[j]!=i&&b1[j]!=b3[i]&&b1[j])ans=max(ans,a[i]+a[j]+a[b3[i]]+a[b1[j]]);
	if(b2[j]!=i&&b2[j]!=b3[i]&&b2[j])ans=max(ans,a[i]+a[j]+a[b3[i]]+a[b2[j]]);
	if(b3[j]!=i&&b3[j]!=b3[i]&&b3[j])ans=max(ans,a[i]+a[j]+a[b3[i]]+a[b3[j]]);
}
int main(){
	freopen("csp2022_holiday.in","r",stdin);
	freopen("csp2022_holiday.out","w",stdout);
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=m;i++)
	{
		ll x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		dl[i][i]=0;
		e[i]=1;
		for(ll j:v[i])
		{
			p.push(j);
			dl[i][j]=1;
			e[j]=1;
		}
		while(p.size())
		{
			ll x=p.front();
			p.pop();
			for(ll j:v[x])
			{
				if(e[j]==0)
				{
					p.push(j);
					dl[i][j]=dl[i][x]+1;
					e[j]=1;
				}
			}
		}
		memset(e,0,sizeof(e));
	}
	e[1]=1;
	dfs(1,1,0);
	for(int i=2;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(dl[i][j]<=k+1)
			{
				if(b1[i]!=j&&b1[i])
					dou1(i,j);
				if(b2[i]!=j&&b2[i])
					dou2(i,j);
				if(b3[i]!=j&&b3[i])
					dou3(i,j);
			}
	cout<<ans;
	return 0;
}