Atcoder AGC 012 B Splatter Painting 题解

题目大意

给你 \(n\) 个点 \(m\) 条边的无向图，然后 \(q\) 次操作，每次给出一组 \(v_{i}\) , \(d_{i}\) , \(c_{i}\), 表示将以 \(v_{i}\) 为中心点 ， 距离不超过 \(d_{i}\)的节点染成 \(c_{i}\) 的颜色

解法

因为有 \(q_{}\) 次操作，所以很自然想到读入询问后逆过来染色 ，加上判断条件可减去很多不必要操作；

在搜索过程中处理 \(cor[i][j]\) 的判断条件，表示以 \(i\) 为中心点，距离不超过 \(j\) 被染成了 \(c\) 的颜色，如果 \(cor[i][j]\) 大于零则证明 \(j\) 范围内已经被染色，不必再搜；

有一个小技巧就是把每个点 \(push\)_\(back\) 道自己的后面，最后 \(cor[i][0]\) 即为所求；

Code

快读打错了真难受

#include<bits/stdc++.h>

typedef long long ll;

const int maxn = 1e5 + 10;

int n, m, a, b, q, cor[maxn][14], qwq[maxn], qaq[maxn], c[maxn];

std::vector <int> pb[maxn];

void Work(int st, int deep, int cl)
{
    if(deep == -1) return;
    if(cor[st][deep]) return;
    cor[st][deep] = cl;
    for(int i = 0; i < pb[st].size(); ++ i) Work(pb[st][i], deep-1, cl);
}

int read()
{
    int x=0, ch= getchar(), f=1;
    while(!isdigit(ch)) if(ch == '-')f = -1, ch = getchar();
    while(isdigit(ch)) x = x *10 + ch-'0', ch = getchar();
    return x * f;
} 

int main()
{
    n=read(), m=read();
    for(int i=1;i<=m;i++) a=read(), b=read(), pb[a].push_back(b), pb[b].push_back(a);
    for(int i=1;i<=n;i++) pb[i].push_back(i);
    q=read();
    for(int i=1;i<=q;i++) qwq[i]=read(), qaq[i] = read(), c[i] = read();
    for(int i=q;i>=1;i--) Work(qwq[i], qaq[i], c[i]);
    for(int i=1;i<=n;i++) std::cout<<cor[i][0]<<std::endl;
    return 0;
}

Atcoder AGC 012 B Splatter Painting 题解

原文：https://www.cnblogs.com/-52hz/p/11787832.html