记录编号	576415	评测结果	AAAAA
题目名称	[NOI 1999]最优连通子集	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-10-08 18:55:22	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
int n, x[1010], y[1010], z[1010], f[1010], maxx, maxy, ans;
bool vis[1010];
vector<int> cd[1010];
int tx[4] = {0, 0, 1, -1}, ty[4] = {1, -1, 0, 0};
void dfs(int nx) {
	f[nx] = z[nx];
	for(int i = 0; i < cd[nx].size(); i ++) {
		int u = cd[nx][i];
		if(vis[u]) {
			continue;
		}
		vis[u] = 1;
		dfs(u);
		f[nx] += max(0, f[u]);
	}
}
signed main() {
 	freopen("subset.in", "r", stdin);
 	freopen("subset.out", "w", stdout);
	cin >> n;
	memset(f, -0x3f, sizeof(f));
	for(int i = 1; i <= n; i ++) {
		cin >> x[i] >> y[i] >> z[i];
		maxx = max(maxx, x[i]);
		maxy = max(maxy, y[i]);
	}
	for(int i = 1; i <= n; i ++) {
		x[i] += maxx;
		y[i] += maxy;
	}
	for(int i = 1; i <= n; i ++) {
		for(int j = i + 1; j <= n; j ++) {
			if(abs(x[i] - x[j]) + abs(y[i] - y[j]) == 1) {
				cd[i].push_back(j);
				cd[j].push_back(i);
			}
		}
	}
	for(int i = 1; i <= n; i ++) {
		if(!vis[i]) {
			vis[i] = 1;
			dfs(i);
		}
	}
	for(int i = 1; i <= n; i ++) {
		ans = max(ans, f[i]);
	}
	cout << ans;
    return 0;
}