题目描述

题目模拟一个城镇的公交系统。有nnn条公交线路（0<n<200 < n < 200<n<20），ddd辆公交车（0<d<300 < d < 300<d<30），sss个公交站（0<s<500 < s < 500<s<50）。每条线路是循环的，至少有两个站点。公交车同时从各自线路的某个站点出发。当多辆公交车在同一站点相遇时，他们会交换所有已知的信息。初始时，每辆公交车知道一条其他车辆不知道的信息。问题：是否最终每辆公交车都能知道所有信息？

输入格式

输入包含多个数据块。每个数据块的第一行包含三个整数nnn、ddd、sss。接下来2n2n2n行描述nnn条线路：

• 每条线路的第一行：该线路的站点列表（按行驶顺序）。
• 每条线路的第二行：若干对(si,di)(s_i, d_i)(si​,di​)，表示驾驶员did_idi​在线路起始站点sis_isi​出发。
  数据块以0 0 0结束。

输出格式

对于每个数据块，输出一行Yes或No，表示最终是否所有驾驶员都能知晓所有信息。

样例

输入

2 3 5 1 2 3 1 1 2 2 2 3 4 5 2 3 0 0 0

输出

Yes

题目分析

本题的核心是判断信息传播的连通性。可以将每辆公交车视为一个节点，若两辆公交车有可能在某个时间点相遇（即它们在某个站点同时出现），则它们之间有一条边。信息可以通过这些边传播。最终所有公交车都能知晓所有信息当且仅当这些公交车在图中是连通的（即从任意一辆车出发都能到达所有其他车）。

相遇判断

两辆公交车aaa和bbb能否相遇？它们各自沿着固定的循环线路行驶。可以模拟它们未来的位置序列，判断是否存在一个时刻它们在同一站点。由于线路长度有限，最多模拟lcm(La,Lb)\texttt{lcm}(L_a, L_b)lcm(La​,Lb​)个时间步即可。但更简单的方法是：生成两辆车的位置序列（每个时间步的位置），检查是否有相同的站点。

连通性

建立d×dd \times dd×d的邻接矩阵，若两辆车可能相遇，则标记为连通。然后使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法或BFS\texttt{BFS}BFS计算传递闭包，检查所有节点是否与节点111连通。

复杂度分析

d≤30d \le 30d≤30，n≤20n \le 20n≤20，s≤50s \le 50s≤50，模拟相遇判断O(O(O(线路长度2)^2)2)，Floyd-Warshall\texttt{Floyd-Warshall}Floyd-WarshallO(d3)O(d^3)O(d3)，完全可接受。

代码实现

// Gossiping// UVa ID: 521// Verdict: Accepted// Submission Date: 2017-05-04// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structdriver{intline,start;};vector<vector<int>>busLines(40,vector<int>());driver drivers[40];boolconnected[40][40];intn,d,s,si,di;boolexchanged(inta,intb){if(a==b)returntrue;intaline=drivers[a].line,bline=drivers[b].line;inttotal=busLines[aline].size()*busLines[bline].size();vector<int>s1;while(s1.size()<total){for(inti=drivers[a].start;i<busLines[aline].size();i++)s1.push_back(busLines[aline][i]);for(inti=0;i<drivers[a].start;i++)s1.push_back(busLines[aline][i]);}vector<int>s2;while(s2.size()<total){for(inti=drivers[b].start;i<busLines[bline].size();i++)s2.push_back(busLines[bline][i]);for(inti=0;i<drivers[b].start;i++)s2.push_back(busLines[bline][i]);}for(inti=0;i<total;i++)if(s1[i]==s2[i])returntrue;returnfalse;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);istringstream iss;string line;while(getline(cin,line)){iss.clear();iss.str(line);iss>>n>>d>>s;if(n==0)break;memset(connected,false,sizeof(connected));for(inti=1;i<=n;i++){busLines[i].clear();getline(cin,line);iss.clear();iss.str(line);while(iss>>si)busLines[i].push_back(si);getline(cin,line);iss.clear();iss.str(line);while(iss>>si>>di){for(intj=0;j<busLines[i].size();j++)if(si==busLines[i][j]){drivers[di]=driver{i,j};break;}}}for(inti=1;i<=d;i++)for(intj=i;j<=d;j++)connected[i][j]=connected[j][i]=exchanged(i,j);for(intk=1;k<=d;k++)for(inti=1;i<=d;i++)for(intj=1;j<=d;j++)if(connected[i][k]&&connected[k][j])connected[i][j]=connected[j][i]=true;boolallConnected=true;for(inti=1;i<=d;i++)if(!connected[1][i]){allConnected=false;break;}cout<<(allConnected?"Yes":"No")<<'\n';}return0;}