记录编号 581749 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 [CSP 2022S]假期计划 最终得分 100
用户昵称 Gravatar宇战 是否通过 通过
代码语言 C++ 运行时间 4.213 s
提交时间 2023-08-12 16:10:49 内存使用 173.53 MiB
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,m,kk,maxn=-1;
int d[2501][2501],cnt,dp[2501][4],vis2[2501][6][2501],q[2501][6][6];
int val[2501],vis[2501],head[2501],step[2501];
int que[2501];
struct Edge{
	int next;
	int to;
	int w;
}edge[30001];
void add_edge(int u,int v)
{
	cnt++;
	edge[cnt].to=v;
	edge[cnt].w=1;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
int main()
{
	freopen("csp2022_holiday.in","r",stdin);
	freopen("csp2022_holiday.out","w",stdout);
	memset(d,0x3f,sizeof(d));
	memset(dp,-0x3f,sizeof(dp));
	memset(head,-1,sizeof(head));
	cin>>n>>m>>kk;
	for(int i=2;i<=n;i++)
	{
		cin>>val[i];
		d[i][i]=0;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		add_edge(x,y);
		add_edge(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		memset(step,0,sizeof(step));
		memset(vis,0,sizeof(vis));
		memset(que,0,sizeof(que));
		que[1]=i;
		vis[i]=1;
		int hea=0,tail=1;
		while(hea<tail)
		{
			hea++;
			int u=que[hea];
			int sat=step[hea];
			d[i][u]=sat;
			if(d[i][u]-1>kk) d[i][u]=d[0][0];
			for(int j=head[u];j!=-1;j=edge[j].next)
			{
				int v=edge[j].to;
			
				if(vis[v]==0)
				{
					step[++tail]=step[hea]+1;
					
					que[tail]=v;
					vis[v]=1;
				}
			}
		}
	} 
	for(int i=2;i<=n;i++)
	{
		if(d[1][i]!=d[0][0])
		{
			dp[i][1]=val[i];
			vis2[i][1][i]=1;
			q[i][1][1]=i;
		}
	}
	for(int k=2;k<=4;k++)
	{
		for(int i=2;i<=n;i++)
		{
			int tmp=0;
			for(int j=2;j<=n;j++)
			{
				if(d[i][j]==d[0][0]||i==j||d[i][j]<0) continue;
				if(vis2[j][k-1][i]==1) continue;
				if(dp[j][k-1]!=dp[0][0])
				{
					if(dp[j][k-1]>dp[i][k])
					{
						dp[i][k]=dp[j][k-1];
						tmp=j;
					}
				}
			}
			for(int j=1;j<=n;j++)
			{
				q[i][k][j]=q[tmp][k-1][j];
				vis2[i][k][q[i][k][j]]=1;
				if(q[i][k][j]==0)
				{
					q[i][k][j]=i;
					vis2[i][k][i]=1;
					break;
				}
			}
			dp[i][k]+=val[i];
		}
	}
	for(int i=2;i<=n;i++)
	{
		if(d[i][1]!=d[0][0])
		{
			maxn=max(maxn,dp[i][4]);
		}
	}
	cout<<maxn;
	return 0;
 }