AT2362 [AGC012B] Splatter Painting
題意
給一個n個點m條邊的無向圖，有q次操作 第i次操作，給出v，d，c，把所有到點v的距離不超過d的點都染上顏色c 問最后每個點的顏色 n,
m, q, c <= 100000 d <= 10
資料范圍比較大， 我們如果直接暴力dfs，一直修改顏色一定會超時，然而題目要求的是最后的顏色，正難則反，如果我們倒著來染色，就會發現最后染色的就一定是答案，所以我們只需要倒著去dfs染色，如果這個點沒有被染過色就染，染過色就過，這樣可以省去很大一筆開銷，可以過，
還有一個重要的剪枝就是在dfs時記錄該點在被涂色是距離涂色中心點v的距離r，當這個點再次被搜到時，只需判斷當前的r是否大于之前記錄的r，否則return，（dist陣列記錄的是該點被遍歷的時候剩余的步數是多少，如果該點之前被遍歷過，并且之前到這里的時候還有5步，而這次又走到了這個點，卻只剩下了3步（3 < 5），那么我們已經沒有必要繼續往下走了，因為下面的能到達的點已經全部被之前染過色了并且還沒之前走的遠，）
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 500007, M = 5000007, INF = 0x3f3f3f3f;
int n,m ;
int head[N], ver[M], nex[M], tot;
int ans[N];
struct node{
int v, d, c;
}a[N];
int dist[N];
void add(int x, int y){
ver[tot] = y;
nex[tot] = head[x];
head[x] = tot ++ ;
}
void dfs(int x, int color, int deep){
if(!ans[x])ans[x] = color;
if(deep == 0 || dist[x] >= deep)return ;
dist[x] = deep;
//dist陣列記錄的是x點染過的最遠的距離，那么上面這個[dist[x] >= deep]
//的剪枝的意思就是如果當前x點染過色的最遠距離比當前距離長，那么就回傳
for(int i = head[x]; ~i; i = nex[i]){
int y = ver[i];
dfs(y, color, deep - 1);
}
}
int main(){
scanf("%d%d", &n,&m);
memset(head, -1, sizeof head);
for(int i = 1; i <= m; ++ i){
int x, y;
scanf("%d%d",&x, &y);
add(x, y), add(y, x);
}
int q;
scanf("%d", &q);
for(int i = 1; i <= q; ++ i)
scanf("%d%d%d", &a[i].v, &a[i].d, &a[i].c);
for(int i = q; i >= 1; -- i){
dfs(a[i].v, a[i].c, a[i].d);
}
for(int i = 1; i <= n; ++ i)
printf("%d\n", ans[i]);
puts("");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/5830.html
標籤：其他
上一篇：微信小程式之自定義退出小程式事件 - 點擊頁面某個功能按鈕退出小程式！
下一篇：優先佇列實作哈夫曼編碼