记录编号 |
577291 |
评测结果 |
AAAAAAWWWWWAAAAWWWWA |
题目名称 |
[CSP 2022S]假期计划 |
最终得分 |
55 |
用户昵称 |
nick |
是否通过 |
未通过 |
代码语言 |
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;
}