AtCoder Grand Contest 012 B Splatter Painting （反向处理 + 记忆化）

题意给定一个$n$个点$m$条边的无向图，现在有$q$个操作。对距离$v$不超过$d$的所有点染色，颜色编号为$c$。

　　求每个点最后的颜色状态。

倒过来处理。

记忆化搜索，用$f[x][d]$表示已经对以$x$为中心距离不超过$d$的点进行了染色。

这样保证了对以$x$为中心距离不超过$d$的点进行染色这个行为最多出现一次。

每次对$x$点染色的时候判断是否已经染过色，如果染过就不再染色了。

时间复杂度$O(nd)$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b)	for (int i(a); i >= (b); --i)
#define MP		make_pair
#define fi		first
#define se		second


typedef long long LL;

const int N = 1e5 + 10;

int f[N][11], ret[N];
int a[N], b[N], c[N];
int n, m, k;

vector <int> v[N];

void solve(int x, int y, int z){
	if (~f[x][y]) return;
	if (!ret[x]) ret[x] = z;
	if (y <= 0) return;
	for (auto u : v[x]){
		solve(u, y - 1, z);
	}
	f[x][y] = 1;
}

int main(){

	scanf("%d%d", &n, &m);
	rep(i, 1, m){
		int x, y;
		scanf("%d%d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}

	scanf("%d", &k);
	rep(i, 1, k){
		scanf("%d%d%d", a + i, b + i, c + i);
	}

	memset(f, -1, sizeof f);
	dec(i, k, 1) solve(a[i], b[i], c[i]);
	rep(i, 1, n) printf("%d\n", ret[i]);
	return 0;
}

AtCoder Grand Contest 012 B Splatter Painting （反向处理 + 记忆化）

推荐阅读