比赛 |
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();
}