【AtCoder】【思维】【图论】Splatter Painting（AGC012）

题意：

有一个含有n个点的无向图，所有的点最初颜色均为0。有q次操作，每次操作将v[i]周围的距离小于等于d[i]的点全部都染成颜色c[i]。最后输出每个点的最终的颜色。

数据范围：

1<=n,m,q<=10^5

0<=d[i]<=10

1<=c[i]<=10^5

思路：

看见1<=d[i]<=10，这个条件，第一反应当然是暴力啦。但是如果从一个点总是能够访问所有的节点，那么这就变成O(n^2)了。那么我们应当考虑时间复杂度更加稳定的算法。

然后开始考虑如何优化。倒着扫操作是很容易想到的。然后可以对于每一个点维护一个对于当前已经扫完的操作的最大值。假如说当前在点v，然后当前的d为d[i]，假如说d[i]<=maxd[v]，那么就说明在后面的操作中将当前这一次操作所产生的效果抵消了。于是就可以直接返回了。

经过上述的优化之后，我们发现能够进入一个点并成功进行拓展的条件是d[i]>maxd[v]，那么因为1<=d[i]<=10，所以说就算d[i]从1~10依次排列，也只会对于v点访问最多10次。这样子时间复杂度就变为了稳定的O(10*n+m)，从而稳当了不少。

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 100000

using namespace std;

struct node

{

	int to;

	node *nxt;

}edges[MAXN*2+5];

node *ncnt=&edges[0],*Adj[MAXN+5];

int n,m,q,col[MAXN+5],maxd[MAXN+5];

int V[MAXN+5],D[MAXN+5],C[MAXN+5];

void Init()

{

	memset(maxd,-1,sizeof(maxd));

}

void AddEdge(int u,int v)

{

	node *p=++ncnt;

	p->to=v;

	p->nxt=Adj[u];

	Adj[u]=p;

	node *q=++ncnt;

	q->to=u;

	q->nxt=Adj[v];

	Adj[v]=q;

}

void DFS(int u,int d,int c)

{

	if(col[u]==0)//没有赋过值才赋值

		col[u]=c;

	if(maxd[u]>=d)//判断当前操作是否被后面的操作覆盖了

		return;

	if(d==0)//到达能够赋值的边界了

		return;

	maxd[u]=d;

	for(node *p=Adj[u];p!=NULL;p=p->nxt)

	{

		int v=p->to;

		DFS(v,d-1,c);//d--,继续赋值

	}

}

int main()

{

	Init();

	scanf("%d %d",&n,&m);

	int u,v;

	for(int i=1;i<=m;i++)

	{

		scanf("%d %d",&u,&v);

		AddEdge(u,v);

	}

	scanf("%d",&q);

	for(int i=1;i<=q;i++)

		scanf("%d %d %d",&V[i],&D[i],&C[i]);

	for(int i=q;i>=1;i--)//倒着处理

		DFS(V[i],D[i],C[i]);

	for(int i=1;i<=n;i++)

		printf("%d\n",col[i]);

	return 0;

}