[DP记录]AT2362 [AGC012B] Splatter Painting

**题意** ： 给一个 $n$ 个点 $m$ 条边的无向图。 有 $q$ 次操作，每次操作，给出 $u,d,c$，把到点 $u$ 距离 $\leq d$ 的点都染上颜色 $c$。 求最后每个点的颜色。 $n,m,q\leq 10^5,d\leq 10$ ，时限$\texttt{2s}$。 ------------ 咋 B 题都卡啊……其实看到 $d$ 的范围就应该排除很多做法的。 将询问倒过来做，这样某个点一旦被染色，就不会再改变。 记 $\{u,d\}$ 表示到点 $u$ 距离 $\leq d$ 的集合。注意到 $\{u,d\}=∪_{u\rightarrow v}\{v,d-1\}$。 记 $f[u][k]$ 为覆盖 $\{u,d\}$ 的最晚的操作。 从 $f[u][k]$ 向 $u\rightarrow v$ 的 $f[v][k-1]$ 转移。(按照 $k$ 从大到小的顺序) 复杂度为 $O\big((n+m)d\big)$。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #define pb push_back #define MaxN 100500 using namespace std; int n,m,q,c[MaxN],f[MaxN][12]; vector<int> g[MaxN]; int main() { scanf("%d%d",&n,&m); for (int i=1,u,v;i<=m;i++){ scanf("%d%d",&u,&v); g[u].pb(v);g[v].pb(u); } scanf("%d",&q); for (int i=1,u,d;i<=q;i++){ scanf("%d%d%d",&u,&d,&c[i]); f[u][d]=i; } for (int k=10;k;k--) for (int u=1;u<=n;u++) for (int i=0;i<g[u].size();i++) f[g[u][i]][k-1]=max(f[g[u][i]][k-1],f[u][k]); for (int i=1;i<=n;i++){ int p=0; for (int k=0;k<=10;k++) p=max(p,f[i][k]); printf("%d\n",c[p]); } return 0; } ``` 咋瞎搜也能过啊 /yun