简答题 偏难
#23549

加工零件 【问题描述】 凯凯的工厂正在有条不紊地生产一种神奇的零件,神奇的零件的生产过程自然也很 神奇。工厂里有n位工人,工人们从1~n编号。某些工人之间存在双…

加工零件

【问题描述】

凯凯的工厂正在有条不紊地生产一种神奇的零件,神奇的零件的生产过程自然也很 神奇。工厂里有n位工人,工人们从1~n编号。某些工人之间存在双向的零件传送 带。保证每两名工人之间最多只存在一条传送带。

如果x号工人想生产一个被加工到第L(L>1)阶段的零件,则所有 与 x 号 工 人 有传送带直接相连的工人,都需要生产一个被加工到第L- 1阶段的零件(但x号工 人自己无需生产第L - 1阶段的零件)。

如果x号工人想生产一个被加工到第1阶段的零件,则所有与x号工人有传送带直接 相连的工人,都需要为x号工人提供一个原材料。

轩 轩 是 1 号工人。现在给出q张工单,第i张工单表示编号为ai的工人想生产 一个第Li阶段的零件。轩轩想知道对于每张工单,他是否需要给别人提供原材料。他 知道聪明的你一定可以帮他计算出来!

【输入格式】

输入文件名为work.in。

第一行两个正整数n,m和q,分别表示工人的数目、传送带的数目和工单的数目。

接下来m行,每行两个正整数u和v,表示编号为u和v的工人之间存在 一条零 件传输带。保证u≠v。

接下来q行,每行两个正整数a和L,表示编号为a的工人想生产 一个第L阶段 的零件。

【输出格式】

输出文件名为work . out。

共q行,每行一个字符串“Yes”或者“No”。如果按照第i张工单生产,需要编号为 1的轩轩提供原材料,则在第i行输出“Yes”;否则在第i行输出“No”。注意输出不含 引号。

【输入输出样例 1】

【输入输出样例1说明】

编号为1的工人想生产第1阶段的零件,需要编号为2的工人提供原材料。

编号为2的工人想生产第1阶段的零件,需要编号为1和3的工人提供原材料。

编号为3的工人想生产第1阶段的零件,需要编号为2的工人提供原材料。

编号为1的工人想生产第2阶段的零件,需要编号为2的工人生产第1阶段的零 件,需要编号为1和3的工人提供原材料。

编号为2的工人想生产第2阶段的零件,需要编号为1和3的工人生产第1阶段 的零件,他/她们都需要编号为2的工人提供原材料。

编号为3的工人想生产第2阶段的零件,需要编号为2的工人生产第1阶段的零件,需要编号为1和3的工人提供原材料。

【输入输出样例2】

【输入输出样例2说明】

编号为1的工人想生产第1阶段的零件,需要编号为2和5的工人提供原材料。

编号为1的工人想生产第2阶段的零件,需要编号为2和5的工人生产第1阶段 的零件,需要编号为1,3,4 的工人提供原材料。

编号为1的工人想生产第3阶段的零件,需要编号为2和5的工人生产第2阶段的零件,需要编号为1,3,4的工人生产第1阶段的零件,需要编号为2,3,4,5 的工人提供 原材料。

编号为1的工人想生产第4阶段的零件,需要编号为2和5的工人生产第3阶段 的零件,需要编号为1,3,4的工人生产第2阶段的零件,需要编号为2,3,4,5 的工人生产 第1阶段的零件,需要全部工人提供原材料。

编号为1的工人想生产第5阶段的零件,需要编号为2和5的工人生产第4阶段 的零件,需要编号为1,3,4的工人生产第3阶段的零件,需要编号为2,3,4,5 的工人生产 第2阶段的零件,需要全部工人生产第1阶段的零件,需要全部工人提供原材料。

【数据规模与约定】

共20个测试点。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int N = 2e5+10;</p><p style="text-align: left;">const int M = 2*N;</p><p style="text-align: left;">typedef long long ll;</p><p style="text-align: left;">int n,m,q;</p><p style="text-align: left;">int head[N],edge[M],ver[M],nex[M] ,tot = 1;</p><p style="text-align: left;">void addEdge(int x,int y,int z){</p><p style="text-align: left;"><span style="white-space:pre"> </span>ver[++tot] = y; edge[tot] = z;</p><p style="text-align: left;"><span style="white-space:pre"> </span>nex[tot] = head[x]; head[x] = tot;</p><p style="text-align: left;">}</p><p style="text-align: left;">int getInt(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int res = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>bool neg = false;</p><p style="text-align: left;"><span style="white-space:pre"> </span>char c = getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(c != '-' &amp;&amp; (c &lt; '0' || c &gt; '9')) c = getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(c == '-') neg = true, c = getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(c &gt;= '0' &amp;&amp; c &lt;= '9') res = res*10+c-'0',c = getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>return neg?-res:res;</p><p style="text-align: left;">}</p><p style="text-align: left;">queue&lt;int&gt; que;</p><p style="text-align: left;">int dis[N],vis[N];</p><p style="text-align: left;">bool solve(int a,int l){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(dis[a] &lt;= l &amp;&amp; !((dis[a]&amp;1) ^ (l&amp;1))) return true;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(dis[a+n] &lt;= l &amp;&amp; !((dis[a+n]&amp;1) ^ (l&amp;1))) return true;</p><p style="text-align: left;"><span style="white-space:pre"> </span>return false;</p><p style="text-align: left;">}</p><p style="text-align: left;">void SPFA(int s){</p><p style="text-align: left;"><span style="white-space:pre"> </span>que.push(s);</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(dis,0x3f,sizeof dis);</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[s] = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(que.size()){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x = que.front(); que.pop();</p><p style="text-align: left;"><span style="white-space:pre"> </span>vis[x] = false;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = head[x];i ;i = nex[i]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int y = ver[i], z = edge[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(dis[y] &gt; dis[x]+z){</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[y] = dis[x]+z;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!vis[y]) que.push(y),vis[y] = true;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p style="text-align: left;">int main(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>n = getInt(); m = getInt(); q = getInt();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1,x,y;i &lt;= m;i++){</p><p style="text-align: left;"><span style="white-space:pre"> </span>x = getInt(); y = getInt();</p><p style="text-align: left;"><span style="white-space:pre"> </span>addEdge(x,y+n,1); addEdge(y+n,x,1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>addEdge(x+n,y,1); addEdge(y,x+n,1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>SPFA(1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>//for(int i = 1;i &lt;= n&lt;&lt;1;i++) cout &lt;&lt; dis[i] &lt;&lt; endl;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1,a,l;i &lt;= q;i++){</p><p style="text-align: left;"><span style="white-space:pre"> </span>a = getInt(); l = getInt();</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(solve(a,l)) puts("Yes");</p><p style="text-align: left;"><span style="white-space:pre"> </span>else puts("No");</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。