比赛 EYOI与SBOI开学欢乐赛5th 评测结果 AAAAA
题目名称 最优连通子集 最终得分 100
用户昵称 今天作业写了没 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-09-16 20:23:57
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int d[2005][2005];
int a,b,j,k,n,p[1005],m=-2100000000;
long long deal(int f,int x,int y)
{
    int ans=p[d[x][y]];
	if(d[x-1][y] && (d[x-1][y]!=f)) ans+=deal(d[x][y],x-1,y);
	if(d[x][y-1] && (d[x][y-1]!=f)) ans+=deal(d[x][y],x,y-1);
	if(d[x+1][y] && (d[x+1][y]!=f)) ans+=deal(d[x][y],x+1,y);
	if(d[x][y+1] && (d[x][y+1]!=f)) ans+=deal(d[x][y],x,y+1);
	ans=max(ans,0);
	m=max(m,ans);
	return ans;
}
void in()
{
	cin>>n;
	cin>>j>>k>>p[0];
	for(int i=1;i<n;i++)
	{
		cin>>a>>b>>p[i];
		a=a+1000-j;
		b=b+1000-k;
		d[a][b]=i;
	}
	j=deal(0,1000,1000);
	cout<<m;
}
int main()
{
	freopen("subset.in","r",stdin);
	freopen("subset.out","w",stdout);
	in();
}