UVa 521 Gossiping

题目描述题目模拟一个城镇的公交系统。有nnn条公交线路0n200 n 200n20ddd辆公交车0d300 d 300d30sss个公交站0s500 s 500s50。每条线路是循环的至少有两个站点。公交车同时从各自线路的某个站点出发。当多辆公交车在同一站点相遇时他们会交换所有已知的信息。初始时每辆公交车知道一条其他车辆不知道的信息。问题是否最终每辆公交车都能知道所有信息输入格式输入包含多个数据块。每个数据块的第一行包含三个整数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≤30n≤20n \le 20n≤20s≤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//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structdriver{intline,start;};vectorvectorintbusLines(40,vectorint());driver drivers[40];boolconnected[40][40];intn,d,s,si,di;boolexchanged(inta,intb){if(ab)returntrue;intalinedrivers[a].line,blinedrivers[b].line;inttotalbusLines[aline].size()*busLines[bline].size();vectorints1;while(s1.size()total){for(intidrivers[a].start;ibusLines[aline].size();i)s1.push_back(busLines[aline][i]);for(inti0;idrivers[a].start;i)s1.push_back(busLines[aline][i]);}vectorints2;while(s2.size()total){for(intidrivers[b].start;ibusLines[bline].size();i)s2.push_back(busLines[bline][i]);for(inti0;idrivers[b].start;i)s2.push_back(busLines[bline][i]);}for(inti0;itotal;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);issnds;if(n0)break;memset(connected,false,sizeof(connected));for(inti1;in;i){busLines[i].clear();getline(cin,line);iss.clear();iss.str(line);while(isssi)busLines[i].push_back(si);getline(cin,line);iss.clear();iss.str(line);while(isssidi){for(intj0;jbusLines[i].size();j)if(sibusLines[i][j]){drivers[di]driver{i,j};break;}}}for(inti1;id;i)for(intji;jd;j)connected[i][j]connected[j][i]exchanged(i,j);for(intk1;kd;k)for(inti1;id;i)for(intj1;jd;j)if(connected[i][k]connected[k][j])connected[i][j]connected[j][i]true;boolallConnectedtrue;for(inti1;id;i)if(!connected[1][i]){allConnectedfalse;break;}cout(allConnected?Yes:No)\n;}return0;}