UVa 318 Domino Effect

题目描述你知道多米诺骨牌除了用来玩多米诺游戏之外还有其他用途吗取一些多米诺骨牌将它们直立摆放成一行骨牌之间只留很小的间隔。如果操作得当你可以推倒第一张骨牌导致所有其他骨牌依次倒下这就是“多米诺效应”这个短语的由来。虽然只有几张骨牌时这样做没什么意义但在八十年代早期一些人走向了另一个极端。他们使用数百万张不同颜色和材料的多米诺骨牌用精心设计的倒下的骨牌图案填满整个大厅创作出短暂的艺术作品。在这些构造中通常不是只有一行骨牌同时倒下。现在你的任务是编写一个程序给定这样一个由多米诺骨牌构成的行系统计算出最后一张骨牌倒下的时间和位置。系统由若干个关键骨牌key dominoes\texttt{key dominoes}key dominoes和连接它们的普通骨牌行组成。当一个关键骨牌倒下时所有连接到它的行也会开始倒下除了已经倒下的那些。当倒下的行到达其他尚未倒下的关键骨牌时这些关键骨牌也会倒下并触发与其相连的行。骨牌行可以从任一端开始倒塌。甚至可能一行从两端同时倒塌此时该行中最后倒下的骨牌位于两个关键骨牌之间的某个位置。假设所有行的倒塌速度均匀。输入格式输入文件包含多个多米诺系统的描述。每个描述的第一行包含两个整数nnn关键骨牌的数量1≤n5001 \leq n 5001≤n500mmm连接关键骨牌的行数关键骨牌编号为111到nnn。任意一对关键骨牌之间最多有一行且图是连通的。接下来的mmm行每行包含三个整数aaa、bbb和lll表示关键骨牌aaa和bbb之间有一行从一端到另一端需要lll秒。每个系统通过推倒111号关键骨牌启动。文件以空系统nm0n m 0nm0结束该行不处理。输出格式对于每个系统输出一行System #1、System #2等。然后输出一行包含最后一张骨牌倒下的时间精确到小数点后一位以及最后一张骨牌倒下的位置要么在关键骨牌处要么在两个关键骨牌之间。按输出样例所示的格式。如果存在多个解输出任意一个。每个系统后输出一个空行。样例输入2 1 1 2 27 3 3 1 2 5 1 3 5 2 3 5 0 0样例输出System #1 The last domino falls after 27.0 seconds, at key domino 2. System #2 The last domino falls after 7.5 seconds, between key dominoes 2 and 3.题目分析问题的本质这是一个图论 单源最短路径问题。关键骨牌作为图的顶点行作为带权边权重为倒塌时间。当111号关键骨牌倒下时倒塌过程沿着边传播。每个关键骨牌在到达时间倒下然后触发其所有邻接边。最后倒下的位置可能是某个关键骨牌其到达时间就是该骨牌倒下的时间某条边的中间位置当该边从两端同时倒塌时最后倒下的是边的中点关键观察设dist[i]dist[i]dist[i]为从111号关键骨牌出发到达关键骨牌iii的最短时间即该骨牌倒下的时间。由于所有边都有正权重可以使用Dijkstra\texttt{Dijkstra}Dijkstra算法计算。对于一条连接aaa和bbb、长度为lll的边如果dist[a]dist[a]dist[a]和dist[b]dist[b]dist[b]是骨牌aaa和bbb的倒下时间则两边开始向对方传播的时间分别为dist[a]dist[a]dist[a]和dist[b]dist[b]dist[b]如果∣dist[a]−dist[b]∣≥l|dist[a] - dist[b]| \ge l∣dist[a]−dist[b]∣≥l则这一边不会在中间相遇一端在另一端开始之前就完全倒下了。此时最后倒下的位置在端点处。如果∣dist[a]−dist[b]∣l|dist[a] - dist[b]| l∣dist[a]−dist[b]∣l则两端在中间某点相遇。设相遇时间ttt满足t−dist[a]t−dist[b]l ⟹ 2tldist[a]dist[b] ⟹ tldist[a]dist[b]2 t - dist[a] t - dist[b] l \implies 2t l dist[a] dist[b] \implies t \frac{l dist[a] dist[b]}{2}t−dist[a]t−dist[b]l⟹2tldist[a]dist[b]⟹t2ldist[a]dist[b]​该相遇点距离aaa为t−dist[a]t - dist[a]t−dist[a]。算法步骤使用Dijkstra\texttt{Dijkstra}Dijkstra计算从111出发到所有关键骨牌的最短路径dist[i]dist[i]dist[i]检查所有关键骨牌记录max⁡(2×dist[i])\max(2 \times dist[i])max(2×dist[i])对应骨牌处的最后倒下时间乘222是为了统一使用整数比较检查所有边对于每条边(a,b,l)(a,b,l)(a,b,l)计算wasteddist[a]dist[b]lwasted dist[a] dist[b] lwasteddist[a]dist[b]l如果wastedmaxWastedTimewasted maxWastedTimewastedmaxWastedTime则更新最后倒下的位置为这条边的中点输出结果时间除以222得到实际秒数判断奇偶确定小数位算法复杂度分析时间复杂度Dijkstra\texttt{Dijkstra}Dijkstra算法O(mlog⁡n)O(m \log n)O(mlogn)使用优先队列检查所有骨牌和边O(nm)O(n m)O(nm)总复杂度O(mlog⁡n)O(m \log n)O(mlogn)n500n 500n500完全可行空间复杂度邻接表O(nm)O(n m)O(nm)距离数组O(n)O(n)O(n)总空间复杂度O(nm)O(n m)O(nm)正确性证明引理 1Dijkstra\texttt{Dijkstra}Dijkstra算法正确计算出从111到每个关键骨牌的最短时间。证明边权为正Dijkstra\texttt{Dijkstra}Dijkstra算法保证得到最短路径。□\square□引理 2关键骨牌iii的最后倒下时间为dist[i]dist[i]dist[i]。证明dist[i]dist[i]dist[i]是从111到iii的最短时间。由于所有边同时开始传播到达iii的最早时间就是dist[i]dist[i]dist[i]而iii一旦到达就立即倒下。□\square□引理 3对于边(a,b,l)(a,b,l)(a,b,l)如果∣dist[a]−dist[b]∣l|dist[a] - dist[b]| l∣dist[a]−dist[b]∣l则边上的最后倒下时间为(ldist[a]dist[b])/2(l dist[a] dist[b])/2(ldist[a]dist[b])/2位置在距aaa为(ldist[b]−dist[a])/2(l dist[b] - dist[a])/2(ldist[b]−dist[a])/2处。证明设tadist[a]t_a dist[a]ta​dist[a]tbdist[b]t_b dist[b]tb​dist[b]。从两端同时向中间传播相遇点满足xylx y lxyltaxtbytt_a x t_b y tta​xtb​yt。解得t(ltatb)/2t (l t_a t_b)/2t(lta​tb​)/2x(ltb−ta)/2x (l t_b - t_a)/2x(ltb​−ta​)/2。□\square□引理 4最后倒下的位置要么是某个关键骨牌要么是某条边的中点。证明最后倒下的位置是“最后被覆盖”的点这要么是最后一个被到达的关键骨牌要么是某条边上从两端传播的交点。□\square□参考代码// Domino Effect// UVa ID: 318// Verdict: Accepted// Submission Date: 2016-07-02// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constlonglongintMAX_INTnumeric_limitsint::max();// 边结构体用于 Dijkstrastructedge{intto;longlongintweight;// 优先队列按权重升序booloperator(edge x)const{returnweightx.weight;}};// 行结构体存储原始边信息structlink{intfrom,to;longlongintseconds;};intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intn,m,cases0;intfrom,to,seconds;longlongintdistances[510];while(cinnm,n){// 初始化距离为无穷大fill(distances,distances510,MAX_INT);// 邻接表存储图vectorvectoredgeedges(n1);// 存储原始边信息用于检查边中点vectorlinklinks;// 读取输入for(inti1;im;i){cinfromtoseconds;edges[from].push_back((edge){to,seconds});edges[to].push_back((edge){from,seconds});links.push_back((link){from,to,seconds});}// Dijkstra 算法求单源最短路径distances[1]0;priority_queueedgeunvisited;unvisited.push((edge){1,0});while(!unvisited.empty()){edge vunvisited.top();unvisited.pop();for(autoe:edges[v.to])if(distances[v.to]e.weightdistances[e.to]){distances[e.to]distances[v.to]e.weight;unvisited.push((edge){e.to,distances[e.to]});}}// 检查关键骨牌处的最后倒下时间intstartKey1,endKey1;longlongintmaxWastedTime0;for(inti1;in;i)if(2*distances[i]maxWastedTime){startKeyendKeyi;maxWastedTime2*distances[i];}// 检查边上的最后倒下时间for(autol:links){// 从两端传播的相遇时间 (dist[a] dist[b] l) / 2// 乘以 2 用整数比较longlongintwastedSecondsdistances[l.from]distances[l.to]l.seconds;if(wastedSecondsmaxWastedTime){startKeymin(l.from,l.to);endKeymax(l.from,l.to);maxWastedTimewastedSeconds;}}// 输出结果coutSystem #casesendl;coutThe last domino falls after maxWastedTime/2;cout(maxWastedTime%2?.5:.0) seconds, ;if(startKeyendKey)coutat key domino endKey.endl;elsecoutbetween key dominoes startKey and endKey.endl;coutendl;}return0;}总结本题的核心在于最短路径关键骨牌倒下时间等于从111出发的最短时间边上的传播当两端传播时间差小于边长时会在中间相遇统一整数计算将所有时间乘以222避免浮点精度问题关键点回顾知识点说明图模型关键骨牌为顶点行为边最短路径Dijkstra\texttt{Dijkstra}Dijkstra算法顶点时间dist[i]dist[i]dist[i]为骨牌iii倒下时间边中点t(ldist[a]dist[b])/2t (l dist[a] dist[b])/2t(ldist[a]dist[b])/2整数技巧所有时间乘222用整数运算输出格式保留一位小数注意事项浮点精度通过乘222用整数比较避免浮点误差输出格式注意句点、空行和大小写边界情况n1n 1n1时只有111号骨牌这种“最短路径 边上相遇时间计算”的解题模式在传播类问题中具有典型性。