题目分析本题描述了一个由多个房间组成的房子其中有一只猫和一只老鼠。猫和老鼠各自有一个“家”起始房间。猫只能在有猫门的房间之间单向移动老鼠只能在有老鼠门的房间之间单向移动。猫门和老鼠门是分开的彼此不能混用。题目要求回答两个问题是否存在猫和老鼠的行走路径使得它们在某个房间相遇即是否存在一个房间RRR使得猫可以从它的家出发到达RRR同时老鼠也可以从它的家出发到达RRR。老鼠是否能走一条至少经过两个房间的回路回到自己的家且在整个过程中无论猫怎么走老鼠都不会遇到猫注意这里的关键是老鼠的路径必须保证无论猫做什么都不会与老鼠相遇。这意味着老鼠必须完全避开所有猫能够到达的房间。解题思路问题一的解法第一个问题相对直观。我们需要判断是否存在一个房间使得猫和老鼠都能从各自的家到达该房间。由于房间数量最大为100100100我们可以使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法来计算每对房间之间的可达性或最短路径长度。具体做法用邻接矩阵cat[i][j]\texttt{cat}[i][j]cat[i][j]表示猫从房间iii到房间jjj的最短路径长度。初始时直接有猫门的房间之间设为111自己到自己的距离设为111其余设为一个大数如100001000010000表示不可达。用同样的方式处理老鼠的移动得到mouse[i][j]\texttt{mouse}[i][j]mouse[i][j]。然后运行Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法for(intk0;kroomNumber;k)for(inti0;iroomNumber;i)for(intj0;jroomNumber;j){if(cat[i][k]cat[k][j]cat[i][j])cat[i][j]cat[i][k]cat[k][j];if(mouse[i][k]mouse[k][j]mouse[i][j])mouse[i][j]mouse[i][k]mouse[k][j];}算法结束后遍历所有房间iii如果cat[catHome][i]10000\texttt{cat}[\textit{catHome}][i] 10000cat[catHome][i]10000且mouse[mouseHome][i]10000\texttt{mouse}[\textit{mouseHome}][i] 10000mouse[mouseHome][i]10000则说明猫和老鼠都能到达房间iii可以相遇。输出Y否则输出N。问题二的解法第二个问题更加复杂。老鼠要找到一条从自己家出发、经过至少两个房间、最终回到自己家的回路并且在整个过程中无论猫怎么走老鼠都不会碰到猫。这里的“无论猫怎么走”意味着老鼠的整个路径上的每一个房间都不能是猫能够到达的房间。因为如果某个房间是猫能够到达的那么猫可以选择走到那个房间从而遇到老鼠。因此我们需要首先确定所有猫能够到达的房间从猫的家出发通过猫门可达的房间。这些房间对老鼠来说是禁区。首先标记了所有猫可达的房间for(inti0;iroomNumber;i)if(cat[catHome][i]10000)for(intj0;jroomNumber;j)mouseSecond[j][i]mouseSecond[i][j]0;这里mouseSecond\texttt{mouseSecond}mouseSecond矩阵用于表示在避开猫可达房间的条件下老鼠的移动情况。初始时mouseSecond\texttt{mouseSecond}mouseSecond被设置为000。代码中有一个细节当读取老鼠门时代码将mouseSecond[start−1][end−1]\texttt{mouseSecond}[start-1][end-1]mouseSecond[start−1][end−1]设置为−1-1−1表示存在一条老鼠门并用−1-1−1表示步数相当于每条边的权值为−1-1−1。为什么要用负权值因为题目要求老鼠的回路至少经过两个房间意味着回路中至少包含两条边。如果我们用−1-1−1表示每条边的长度那么一条包含kkk条边的回路的总长度为−k-k−k。求最长的回路相当于求绝对值最大的负数即最负的值。然后我们需要在只使用不在猫可达区域的房间的条件下计算老鼠的Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法。但这里有一个重要的预处理对于那些猫可达的房间我们将其在mouseSecond\texttt{mouseSecond}mouseSecond矩阵中对应的行和列全部清零相当于从图中移除这些房间。接下来在受限的图上再次运行Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法for(intk0;kroomNumber;k)for(inti0;iroomNumber;i)for(intj0;jroomNumber;j)if(mouseSecond[i][k]0mouseSecond[k][j]0mouseSecond[i][k]mouseSecond[k][j]mouseSecond[i][j])mouseSecond[i][j]mouseSecond[i][k]mouseSecond[k][j];注意这里的条件只有当mouseSecond[i][k]0\texttt{mouseSecond}[i][k] 0mouseSecond[i][k]0且mouseSecond[k][j]0\texttt{mouseSecond}[k][j] 0mouseSecond[k][j]0时才进行松弛操作。因为负值表示存在有效的边或路径而000表示不可达或被移除的房间。最后检查mouseSecond[mouseHome][mouseHome]\texttt{mouseSecond}[\textit{mouseHome}][\textit{mouseHome}]mouseSecond[mouseHome][mouseHome]的值。如果这个值≤−2\leq -2≤−2说明存在一条从老鼠家出发回到老鼠家的回路且边数至少为222因为−2-2−2表示222条边−3-3−3表示333条边以此类推。代码中使用abs(mouseSecond[mouseHome][mouseHome])取绝对值然后判断是否≥2\geq 2≥2。关于Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall的应用说明本题使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法有两个目的计算可达性对于第一个问题我们关心的是是否存在一条路径因此用111表示有边∞\infty∞表示无边Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall可以求出任意两点之间的最短路径长度非无穷即可达。计算最长路径回路对于第二个问题通过将边权设为−1-1−1将最长路径问题转化为最短路径问题因为更负的值表示更长的路径。Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall同样可以处理负权边只要没有负权环但这里负权环正是我们想要的表示可以无限循环不过题目只要求至少两个房间的回路所以我们只需要检查是否存在长度为−2-2−2或更负的回路。代码// Cat and Mouse// UVa ID: 274// Verdict: Accepted// Submission Date: 2016-05-15// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intcat[101][101],mouse[101][101],mouseSecond[101][101];introomNumber,catHome,mouseHome;voidfindWalk(){// Floyd-Warshall 算法计算猫和老鼠的可达性最短路径for(intk0;kroomNumber;k)for(inti0;iroomNumber;i)for(intj0;jroomNumber;j){if(cat[i][k]cat[k][j]cat[i][j])cat[i][j]cat[i][k]cat[k][j];if(mouse[i][k]mouse[k][j]mouse[i][j])mouse[i][j]mouse[i][k]mouse[k][j];}// 问题一判断是否存在猫和老鼠都能到达的房间boolfindRoomfalse;for(inti0;iroomNumber;i)if(cat[catHome][i]10000mouse[mouseHome][i]10000){findRoomtrue;break;}cout(findRoom?Y:N);// 问题二预处理移除所有猫能够到达的房间将其置为不可达for(inti0;iroomNumber;i)if(cat[catHome][i]10000)for(intj0;jroomNumber;j)mouseSecond[j][i]mouseSecond[i][j]0;// 在避开猫可达房间的图上使用 Floyd-Warshall 计算最长路径边权为 -1for(intk0;kroomNumber;k)for(inti0;iroomNumber;i)for(intj0;jroomNumber;j)// 只有当中间路径都存在时值为负才进行松弛if(mouseSecond[i][k]0mouseSecond[k][j]0mouseSecond[i][k]mouseSecond[k][j]mouseSecond[i][j])mouseSecond[i][j]mouseSecond[i][k]mouseSecond[k][j];// 检查是否存在从老鼠家出发回到老鼠家的回路至少两条边intlongestWalkabs(mouseSecond[mouseHome][mouseHome]);cout(longestWalk2? Y: N)endl;}intmain(){intcases;cincases;while(cases--){cinroomNumbercatHomemouseHome;catHome--;mouseHome--;// 初始化矩阵for(inti0;iroomNumber;i)for(intj0;jroomNumber;j){cat[i][j]10000;// 大数表示不可达mouse[i][j]10000;mouseSecond[i][j]0;// 0 表示不可达或已被移除}// 自己到自己的距离设为 1cat[catHome][catHome]1;mouse[mouseHome][mouseHome]1;// 读取猫门信息intstart,end;while(cinstartend,start0end0)cat[start-1][end-1]1;// 读取老鼠门信息cin.ignore();string line;while(getline(cin,line),line.length()0){sscanf(line.data(),%d %d,start,end);mouse[start-1][end-1]1;mouseSecond[start-1][end-1]-1;// 用 -1 表示有一条边}findWalk();if(cases)coutendl;}return0;}总结本题的核心在于使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法处理有向图的路径可达性问题。第二个问题需要识别“安全区域”——即猫无法到达的房间集合老鼠只能在这个子图上移动。将最长路径问题转化为带负权的最短路径问题利用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法求解回路。