UVa 380 Call Forwarding

题目描述得益于计算机技术电话系统的功能在过去十年中得到了极大的增强。我们有自动菜单、复杂的应答机、电话会议功能、群组寻址等等。公司电话系统的一个常见功能是设置呼叫转移。NHC\texttt{NHC}NHC公司的电话都有四位数字的分机号。员工可以通过电话界面输入信息来设置呼叫转移。输入信息包括他们的分机号、离开时间、离开时长以及呼叫应转移到的目标分机号。约束条件分机号为四位数字000000000000和999999999999保留特殊用途时间以小时为单位从每年元旦午夜000000000000开始计时最大为878487848784366×24366 \times 24366×24呼叫转移系统在每年年初完全重置用户在XXX时刻设置的时长为YYY的转移在XXX到XYXYXY时间范围内有效包含端点用户不会提交重叠时间的请求尽管用户从自身角度输入正确、清晰、不重叠的信息但如果请求形成循环转发如AAA转给BBBBBB转给CCCCCC转给AAA则会发生退化情况。此时系统会将此类呼叫转移到特殊分机999999999999。输入格式第一行包含整数NNN1≤N≤101 \leq N \leq 101≤N≤10表示要模拟的呼叫转发系统数量。每个系统由000到100100100行请求组成格式为source time duration target。一行以0000作为source表示该部分输入结束。然后是111条或多条呼叫记录格式为time extension时间非递减。一行以9000作为time表示该部分输入结束。输出格式第一行输出CALL FORWARDING OUTPUT。然后每个系统输出SYSTEM N标题之后为每个呼叫输出一行格式为AT dddd CALL TO dddd RINGS dddd。最后一行输出END OF OUTPUT。样例输入2 1111 0100 0200 2222 1111 0301 0500 4444 2222 0200 0200 3333 3333 0250 1000 1111 7777 1000 2000 7777 0000 0050 1111 0150 1111 0200 1111 0225 2222 0270 1111 0320 1111 0320 3333 0900 3000 1250 3333 1250 7777 9000 0000 3000 1111 9000样例输出CALL FORWARDING OUTPUT SYSTEM 1 AT 0050 CALL TO 1111 RINGS 1111 AT 0150 CALL TO 1111 RINGS 2222 AT 0200 CALL TO 1111 RINGS 3333 AT 0225 CALL TO 2222 RINGS 3333 AT 0270 CALL TO 1111 RINGS 9999 AT 0320 CALL TO 1111 RINGS 4444 AT 0320 CALL TO 3333 RINGS 4444 AT 0900 CALL TO 3000 RINGS 3000 AT 1250 CALL TO 3333 RINGS 1111 AT 1250 CALL TO 7777 RINGS 9999 SYSTEM 2 AT 3000 CALL TO 1111 RINGS 1111 END OF OUTPUT题目分析问题的本质这是一个呼叫转移链追踪问题。需要存储每个分机在不同时间段的转发目标对于每个呼叫根据呼叫时间确定当前有效的转移规则沿着转移链追踪直到找到最终响铃的分机检测循环转发将循环中的呼叫导向999999999999数据结构使用mapstring, vectoritem存储每个分机的转发规则。每个规则包含起止时间和目标分机。追踪算法对于呼叫(time, extension)设当前分机current extension使用setstring记录已访问的分机用于检测循环当current有有效的转发规则时如果target已在访问集合中则循环最终为9999否则将current加入集合移动到target输出最终分机参考代码// Call Forwarding// UVa ID: 380// Verdict: Accepted// Submission Date: 2016-07-04// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structitem{string source,time,duration,target;intstart,end;};mapstring,vectoritemitems;intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intcases;cincases;coutCALL FORWARDING OUTPUTendl;for(inti1;icases;i){items.clear();coutSYSTEM iendl;string source,time,duration,target,extension;intstart,end;// 读取转发规则while(cinsource,source!0000){cintimedurationtarget;startstoi(time);endstartstoi(duration);items[source].push_back({source,time,duration,target,start,end});}// 处理呼叫while(cintime,time!9000){cinextension;intcalling_timestoi(time);string next_extensionextension;setstringcalled;// 记录已访问的分机用于检测循环while(items.find(next_extension)!items.end()){boolget_outtrue;// 查找当前分机在呼叫时间的有效转发规则for(autodata:items[next_extension])if(calling_timedata.startcalling_timedata.end){if(called.find(data.target)called.end()){called.insert(data.target);next_extensiondata.target;get_outfalse;}else{// 发现循环get_outtrue;next_extension9999;}break;}if(get_out)break;}coutAT time CALL TO extension RINGS next_extensionendl;}}coutEND OF OUTPUTendl;return0;}