题解 CSP2019-J2T4【加工零件】

这题我们要求的是啥呢？仔细读题可以发现，工人传送带的关系可以看成一个 \(n\) 个点和 \(m\) 条边的无向图，然后对于每组询问 \((a,L)\)，其实就是问：

\(1\) 到 \(a\) 有没有一条长度为 \(L\) 的路径。

我们换个角度思考一下，如果已知 \(1\) 到 \(a\) 有一条长度为 \(S\) 的路径，我们在这条路径上任选一条边重复走一次，那么就会出现一条 \(1\) 到 \(a\) 长度为 \(S+2\)的路径，同理，也会有 \(1\) 到 \(a\) 长度为 \(S+4\)，也会有 \(1\) 到 \(a\) 长度为 \(S+6\) 的路径\(.......\)

那么我们可以知道：若 \(1\) 到 \(a\) 有一条长度为 \(S\) 的路径，其中 \(S \leq L\) 且 \(S\equiv L\pmod{2}\)，那么 \(1\) 到 \(a\) 有一条长度为 \(L\) 的路径。

为了统计更多的信息，我们要使得对于每个 \(a\) 求出的 \(S\) 最小，以及保证奇偶性一致，那么很明显就是分奇\(/\)偶求最短路了。

设 \(d[a][1/0]\) 表示 \(1\) 到 \(a\) 路径长度为奇\(/\)偶的最短路长度，特别的，若 \(1\) 到 \(a\) 没有路径长度为奇\(/\)偶的路径，则 \(d[a][1/0]\) 为正无穷。初始时 \(d[1][0]=0\) ，其他均为正无穷。

考虑到 "奇路径\(+1\)为偶路径" 与 "偶路径\(+1\)为奇路径" ，那么对于一条边 \((u,v)\) ，我们都可以尝试用 \(d[u][0]+1\) 去更新 \(d[v][1]\)，尝试用 \(d[u][1]+1\) 更新 \(d[v][0]\)。

这里拿 \(SPFA\) 做例子（别问为什么是这个死了的算法，问就是边权为 \(1\) 卡不掉，\(dijkstra\)同），具体的，在 \(SPFA\) 的过程中，在队列里多维护一个信息，表示松弛该节点时是奇最短路还是偶最短路（记为 \(type \in\{ 0,1\}\) ），对于每次松弛的节点 \(u\) ，扫描 \(u\) 的每一条出边 \((u,v)\) ，尝试用 \(d[u][type]+1\) 更新 \(d[v][type \ xor \ 1]\)，若更新成功且二元组 \((v,type \ xor \ 1)\) 不在队中，再把\((v,type \ xor \ 1)\)插入队尾，直至队列为空，这样就处理好了 \(d\) 数组。

对于每组询问\((a,L)\)， \(Θ(1)\) 比较 \(d[a][L\&1]\) 与 \(L\) 的大小关系即可。

需要注意的是，可能会有 \(1\) 号节点与所有点都没有连边的毒瘤数据，此时根据题意，当 \(a=1\) 时，无论 \(L\) 的取值，答案都是 \(NO\) ，但初始化时 \(d[1][0]=0\) ，如果 \(L\equiv 0\pmod{2}\)，则会输出 \(YES\)。此处需要特判一下，判断 \(1\) 号节点与所有点都没有连边的情况只需判断 \(1\) 号节点的表头是否为 \(0\) 即可（邻接表存边）

Code 部分

\(SPFA\)版本：

#include<cstdio>

#include<cstring>

#include<queue>

#define RI register int

using namespace std;

inline int read()

{

	int x=0,f=1;char s=getchar();

	while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}

	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

	return x*f;

}

const int N=100100,M=200100;

int n,m,Q;

int tot,head[N],ver[M],edge[M],Next[M];

void add(int u,int v,int w)//邻接表

{

	ver[++tot]=v;    edge[tot]=w;    Next[tot]=head[u];    head[u]=tot;

}

struct data{//队中节点数据

	int type;// 奇/偶 最短路

	int name;//编号

};

int d[N][2];

int vis[N][2];

void SPFA()

{

	memset(d,0x3f,sizeof(d));

	d[1][0]=0;

	queue<data>q;

	q.push((data){0,1});

	while(q.size())

	{

		data u=q.front();q.pop();vis[u.name][u.type]=0;//取出队头

		for(RI i=head[u.name];i;i=Next[i])

		{

			int v=ver[i],w=edge[i];

			if(d[u.name][u.type]+w<d[v][u.type^1])//能够更新

			{

				d[v][u.type^1]=d[u.name][u.type]+w;//更新

				if(!vis[v][u.type^1])

				{

					vis[v][u.type^1]=1;//标记

					q.push((data){u.type^1,v});//入队

				}

			}

		}

	}

}

int main()

{

	n=read(),m=read(),Q=read();

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

	{

		int u=read(),v=read();

		add(u,v,1),add(v,u,1);//加边

	}

	SPFA();

	while(Q--)

	{

		int a=read(),L=read();

		if(d[a][L&1]<=L&&(a!=1||head[a])/*特判*/)

			puts("Yes");

		else

			puts("No");

	}

	return 0;

}

\(dijkstra\)版本：

#include<cstdio>

#include<cstring>

#include<algorithm>

#define RI register int

using namespace std;

inline int read()

{

	int x=0,f=1;char s=getchar();

	while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}

	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

	return x*f;

}

const int N=100100,M=200100;

int n,m,Q;

int tot,head[N],ver[M],edge[M],Next[M];

void add(int u,int v,int w)//邻接表

{

	ver[++tot]=v;    edge[tot]=w;    Next[tot]=head[u];    head[u]=tot;

}

int len;

struct data{//堆中节点数据

	int tpye;// 奇/偶 最短路

	int dis;//长度

	int name;//编号

}heap[N];

void put(data x)//入堆操作

{

	heap[++len]=x;

	int now=len;

	while(now)

	{

		int nxt=now/2;

		if(heap[nxt].dis<=heap[now].dis)break;

		swap(heap[nxt],heap[now]);

		now=nxt;

	}

}

void change()//堆顶出堆

{

	heap[1]=heap[len--];

	int now=1;

	while(now*2<=len)

	{

		int nxt=now*2;

		if(nxt+1<=len&&heap[nxt].dis>heap[nxt+1].dis)nxt++;

		if(heap[now].dis<=heap[nxt].dis)break;

		swap(heap[now],heap[nxt]);

		now=nxt;

	}

}

int d[N][2];

int vis[N][2];

void dijkstra()

{

	memset(d,0x3f,sizeof(d));

	d[1][0]=0;

	put((data){0,0,1});

	while(len)

	{

		data u=heap[1];change();//取出堆顶

		if(vis[u.name][u.tpye])continue;

		vis[u.name][u.tpye]=1;//标记

		for(RI i=head[u.name];i;i=Next[i])

		{

			int v=ver[i],w=edge[i];

			if(d[u.name][u.tpye]+w<d[v][u.tpye^1])//能够更新

			{

				d[v][u.tpye^1]=d[u.name][u.tpye]+w;//更新

				put((data){u.tpye^1,d[v][u.tpye^1],v});//入堆

			}

		}

	}

}

int main()

{

	n=read(),m=read(),Q=read();

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

	{

		int u=read(),v=read();

		add(u,v,1),add(v,u,1);//加边

	}

	dijkstra();

	while(Q--)

	{

		int a=read(),L=read();

		if(d[a][L&1]<=L&&(a!=1||head[a])/*特判*/)

			puts("Yes");

		else

			puts("No");

	}

	return 0;

}

巴特西

题解 CSP2019-J2T4【加工零件】

Code 部分

Thanks for watching

最新文章

热门文章