3175259_ac_15ms_312k.cc

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

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

using namespace std;

int n, flag, maxf;
vector <int> tree[1001], flor[1001];
int point[1001][3];
int visited[1001];
int num[1001];
int fa[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;
}

void dfs(int v,int b,int father)
{
	int i;

	flor[b].push_back(v);
	if(b>maxf)
		maxf = b;
	visited[v] = 1;
	fa[v] = father;
	for(i = 0; i < tree[v].size(); i++)
	{
		if(visited[tree[v][i]]==0)
		{
			dfs(tree[v][i],b+1,v);
		}
	}
}

int MAX(int a,int b)
{
	return a < b ? b : a;
}

int main()
{
	int i, j, k;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		tree[i].clear();
		flor[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);
			}
		}
	}
	maxf = -1;
	memset(visited,0,sizeof(visited));
	dfs(0,0,-1);
	for(i = maxf; i >= 0; i--)
	{
		for(j = 0; j < flor[i].size(); j++)
		{
			if(tree[flor[i][j]].size()==0)
			{
				num[flor[i][j]] = MAX(point[flor[i][j]][2],0);
			}
			else
			{
				int v = point[flor[i][j]][2];
				for(k = 0; k < tree[flor[i][j]].size(); k++)
				{
					if(tree[flor[i][j]][k]==fa[flor[i][j]])
						continue;
					v += MAX(0,num[tree[flor[i][j]][k]]);
				}
				num[flor[i][j]] = MAX(v,0);
			}
		}
	}
	printf("%d\n",num[0]);
	return 0;
}