3175059_wa.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>
#define inf -100000000

using namespace std;

int n, flag;
vector <int> tree[1001];
int point[1001][3];
int visited[1001];
int num[1001];

int dis(int i,int j)
{
	int a = point[i][0]-point[j][0];
	int b = point[i][1]-point[j][1];
	if(a < 0)	a = -a;
	if(b < 0)	b = -b;
	return a+b;
}

int dfs(int v)
{
	int i;

	num[v] = point[v][2];
	visited[v] = flag;
	for(i = 0; i < tree[v].size(); i++)
	{
		if(visited[tree[v][i]]!=flag)
		{
			num[v] += dfs(tree[v][i]);
		}
	}
	return num[v];
}

int main()
{
	int i, j, tmp, ans;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		tree[i].clear();
		scanf("%d%d%d",&point[i][0],&point[i][1],&point[i][2]);
	}
	flag = 1;
	for(i = 0; i < n; i++)
	{
		for(j = i+1; j < n; j++)
		{
			if(dis(i,j)==1)
			{
				tree[i].push_back(j);
				tree[j].push_back(i);
			}
		}
	}
	ans = inf;
	for(i = 0; i < n; i++)
	{
		dfs(i);
		tmp = point[i][2];
		for(j = 0; j < tree[i].size(); j++)
		{
			if(num[tree[i][j]] > 0)
			{
				tmp += num[tree[i][j]];
			}
		}
		if(tmp > ans)
		{
			ans = tmp;
		}
		flag++;
	}
	printf("%d\n",ans);
	return 0;
}