gfojzy

题目如下：

Splatter Painting

有一个由N个顶点编号为1到N和M个边缘组成的简单的无向图。最初，所有顶点都以彩色0绘制。第i个边缘双向连接两个顶点ai和bi。每个边的长度为1。

Squid在此图上执行了Q操作。在第i个操作中，他以颜色ci重新绘制距离顶点vi的距离内的所有顶点。

在Q操作后查找每个顶点的颜色。

1≤N,M,Q≤105 1≤ai,bi,vi≤N ai≠bi 0≤di≤10 1≤ci≤105

分析

本题的暴力可以轻松写出，注意到一个点只有最后一次染色有效，所以可以从后往前做，如果已被染色则跳过 发现可以记录距此点染色的结点的最大距离d[i] 举个例子： d[6]=1,d[1]=2 然后就a了

完整ac代码1

if(e[y]<z-1)Q.push((Dis){y,z-1});//判断是否应该入队，则不用bo【】数组标记是否在队列中 #include<cstdio> #include<iostream> #include<queue> #include<cstring> #define N 100010 using namespace std; struct Dis{ int x,z; }; queue<Dis>Q; int a[N],c[N],d[N],e[N],f[N],num,h[N],n,m,p,q,t,col; struct Edge{ int p,q,n; }b[N*2]; void ljb(int p,int q){ b[++num].n=h[p]; h[p]=num; b[num].p=p; b[num].q=q; } void Bfs(){ int x,y,z; while(!Q.empty()){ x=Q.front().x; z=Q.front().z; Q.pop(); // printf("%d %d\n",x,z); if(!f[x])f[x]=col; e[x]=max(e[x],z); if(z==0)continue; for(int i=h[x];i!=0;i=b[i].n){ y=b[i].q; if(e[y]<z-1)Q.push((Dis){y,z-1}); } } } int main(){ // freopen("data.txt","r",stdin); memset(e,-1,sizeof(e)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&p,&q); ljb(p,q); ljb(q,p); } scanf("%d",&t); for(int i=1;i<=t;i++)scanf("%d%d%d",&a[i],&d[i],&c[i]); for(int i=t;i>=1;i--){ if(e[a[i]]>=d[i])continue; col=c[i]; Q.push((Dis){a[i],d[i]}); Bfs(); } // for(int i=1;i<=n;i++)printf("%d %d\n",i,e[i]); for(int i=1;i<=n;i++)printf("%d\n",f[i]); }

完整ac代码2

比代码1效率低 多了一个bo【】标记是否入队（其实是多余的）

#include<cstdio> #include<iostream> #include<queue> #include<cstring> #define N 100010 using namespace std; struct Dis{ int x,z; }; queue<Dis>Q; int a[N],c[N],d[N],e[N],f[N],num,h[N],n,m,p,q,t,col; bool bo[N]; struct Edge{ int p,q,n; }b[N*2]; void ljb(int p,int q){ b[++num].n=h[p]; h[p]=num; b[num].p=p; b[num].q=q; } void Bfs(){ int x,y,z; while(!Q.empty()){ x=Q.front().x; z=Q.front().z; Q.pop(); printf("%d %d\n",x,z); if(!f[x])f[x]=col; if(z<=e[x]||z==0)continue; e[x]=z; for(int i=h[x];i!=0;i=b[i].n){ y=b[i].q; if(!bo[y]){ Q.push((Dis){y,z-1}); bo[y]=1; } } } } int main(){ // freopen("data.txt","r",stdin); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d%d",&p,&q); ljb(p,q); ljb(q,p); } scanf("%d",&t); for(int i=1;i<=t;i++)scanf("%d%d%d",&a[i],&d[i],&c[i]); for(int i=t;i>=1;i--){ memset(bo,0,sizeof(bo)); if(e[a[i]]>=d[i])continue; col=c[i]; Q.push((Dis){a[i],d[i]}); bo[a[i]]=1; Bfs(); } for(int i=1;i<=n;i++)printf("%d\n",f[i]); }