UVa 405 Message Routing

题目描述题目模拟了x.400\texttt{x.400}x.400消息处理系统中MTA\texttt{MTA}MTAMessage Transfer Agent\texttt{Message Transfer Agent}Message Transfer Agent消息传输代理的路由功能。每个MTA\texttt{MTA}MTA维护一个路由表用于根据消息的O/R\texttt{O/R}O/R名称Originator/Recipient name\texttt{Originator/Recipient name}Originator/Recipient name发件人/收件人名称将消息转发到下一个MTA\texttt{MTA}MTA或本地投递。O/R\texttt{O/R}O/R名称由四个组件组成按范围从宽到窄依次为C\texttt{C}CCountry\texttt{Country}Country国家ADMD\texttt{ADMD}ADMDAdministrative Management Domain\texttt{Administrative Management Domain}Administrative Management Domain行政管理域PRMD\texttt{PRMD}PRMDPrivate Management Domain\texttt{Private Management Domain}Private Management Domain私有管理域O\texttt{O}OOrganization Name\texttt{Organization Name}Organization Name组织名称每个MTA\texttt{MTA}MTA的路由表包含若干条目每个条目指向一个相邻MTA\texttt{MTA}MTA并包含四个组件的匹配模式。匹配模式可以是具体字符串也可以是通配符*匹配任意内容。路由时按从上到下的顺序查找第一个匹配的条目然后将消息转发到该条目指定的MTA\texttt{MTA}MTA。路由可能出现的三种结果本地投递如果匹配到的MTA\texttt{MTA}MTA就是当前MTA\texttt{MTA}MTA本身则消息被成功投递。循环路由如果检测到消息曾经经过同一个MTA\texttt{MTA}MTA即形成环路则产生循环路由错误。无法路由如果路由表中没有任何条目匹配消息的O/R\texttt{O/R}O/R名称则产生无法路由错误。输入格式每个测试场景scenario\texttt{scenario}scenario的输入格式如下第一行一个整数MMM1≤M≤101 \le M \le 101≤M≤10表示该场景中MTA\texttt{MTA}MTA的数量。接下来依次描述每个MTA\texttt{MTA}MTA一行包含MTA\texttt{MTA}MTA名称111到101010个字母左对齐无空格和整数III0≤I≤90 \le I \le 90≤I≤9表示该MTA\texttt{MTA}MTA路由表的条目数。MTA\texttt{MTA}MTA名称占第111到101010列III在第121212列。接下来III行每行包含相邻MTA\texttt{MTA}MTA名称第111到101010列以及四个O/R\texttt{O/R}O/R组件分别在第151515到242424列、第303030到393939列、第454545到545454列、第606060到696969列。每个组件由111到101010个字母组成或为单个星号*通配符。所有MTA\texttt{MTA}MTA描述结束后一行包含一个整数NNN0N327680 N 327680N32768表示消息的数量。接下来NNN行每行描述一条消息起始MTA\texttt{MTA}MTA名称第111到101010列和四个O/R\texttt{O/R}O/R组件列位置同上。消息从该起始MTA\texttt{MTA}MTA开始模拟路由。输出格式对于每个场景首先输出一行Scenario # X其中XXX从111开始递增。接下来NNN行每行对应一条消息格式为消息编号 -- 结果描述结果描述为以下三种之一delivered to MTA_NAMEcircular routing detected by MTA_NAMEunable to route at MTA_NAME其中MTA_NAME替换为生成报告的MTA\texttt{MTA}MTA名称。每条消息输出后在场景末尾输出一个空行。样例输入5 NAULINS 3 HOUSTON US SHIP * UH DOWNTOWN NAULINS US SHIP * UNO DALLAS US AIR UT * HOUSTON 4 HOUSTON US * UH UHDT SANANTONIO US BUS UT UTSA DALLAS US AIR UT * NAULINS US SHIP * UNO DALLAS 7 DALLAS US * UT TDD DALLAS US * UT TDA HOUSTON US * UH * SANANTONIO US AIR UT UTSA OKLAHOMA US BUS * OU NAULINS US AIR * UNO HOUSTON US SHIP ** OKLAHOMA 3 OKLAHOMA US ** OU DALLAS US AIR ** SANANTONIO US BUS ** SANANTONIO 5 HOUSTON *** UNO HOUSTON US BUS UH * DALLAS US AIR ** SANANTONIO US * UT UTSA OKLAHOMA US BUS UH UHDT 5 SANANTONIO US AIR COLLEGE UNO OKLAHOMA US BUS UH UHDT DALLAS US SHIP COLLEGE UNO NAULINS US AIR COLLEGE OU HOUSN US AIR UT UTSA输出Scenario # 1 1 -- unable to route at HOUSTON 2 -- delivered to HOUSTON 3 -- delivered to NAULINS 4 -- unable to route at NAULINS 5 -- circular routing detected by DALLAS题目分析本题的核心是实现一个多MTA\texttt{MTA}MTA路由模拟系统需要处理路由表的匹配规则、循环检测和错误处理。路由匹配规则每个MTA\texttt{MTA}MTA的路由表是一个有序列表从上到下。对于给定的消息O/R\texttt{O/R}O/R名称(C,ADMD,PRMD,O)(C, \textit{ADMD}, \textit{PRMD}, O)(C,ADMD,PRMD,O)依次检查每个路由条目匹配条件为条目的国家组件等于消息的国家组件或者条目国家为*且条目的ADMD\textit{ADMD}ADMD组件等于消息的ADMD\textit{ADMD}ADMD或者为*且条目的PRMD\textit{PRMD}PRMD组件等于消息的PRMD\textit{PRMD}PRMD或者为*且条目的组织组件等于消息的组织组件或者为*四个条件同时满足时该条目匹配成功。注意*匹配任意内容包括空题目未明确空值情况但所有组件均为111到101010个字母无空组件。路由流程从起始MTA\texttt{MTA}MTA开始重复以下步骤在当前MTA\texttt{MTA}MTA的路由表中按顺序查找第一个匹配的条目。如果找不到匹配条目 →无法路由报告当前MTA\texttt{MTA}MTA。如果找到匹配条目如果目标MTA\texttt{MTA}MTA就是当前MTA\texttt{MTA}MTA→本地投递成功。否则检查是否曾经过目标MTA\texttt{MTA}MTA循环检测如果曾经经过 →循环路由错误报告目标MTA\texttt{MTA}MTA。否则记录当前MTA\texttt{MTA}MTA为已访问移动到目标MTA\texttt{MTA}MTA继续循环。循环检测循环检测需要记录已经访问过的MTA\texttt{MTA}MTA但注意是在消息的整个路由路径中一个MTA\texttt{MTA}MTA不能出现两次。一旦第二次到达同一个MTA\texttt{MTA}MTA即检测到循环。实现时可以用一个set\texttt{set}set或KaTeX parse error: Expected EOF, got _ at position 18: …exttt{unordered_̲set}记录已经经过的MTA\texttt{MTA}MTA。每次准备转发到下一个MTA\texttt{MTA}MTA时先检查该目标MTA\texttt{MTA}MTA是否已在集合中如果在 → 循环路由报告目标MTA\texttt{MTA}MTA即检测到循环的MTA\texttt{MTA}MTA。如果不在 → 将当前MTA\texttt{MTA}MTA加入集合然后移动到目标MTA\texttt{MTA}MTA。注意起始MTA\texttt{MTA}MTA是否应预先加入集合根据题目描述“If an MTA detects that it has received a message that it has handled before”检测发生在MTA\texttt{MTA}MTA接收到消息时。因此在进入一个新的MTA\texttt{MTA}MTA时应该先检查该MTA\texttt{MTA}MTA是否已在历史中。但更简便的实现是在准备转发到下一个MTA\texttt{MTA}MTA时检查目标是否已访问过因为当前MTA\texttt{MTA}MTA已经处理过即将离开。参考代码的实现是在匹配到目标MTA\texttt{MTA}MTA后检查目标MTA\texttt{MTA}MTA是否在routed\texttt{routed}routed集合中该集合记录的是已经处理过的MTA\texttt{MTA}MTA。注意它将当前MTA\texttt{MTA}MTA加入集合然后移动到目标MTA\texttt{MTA}MTA。这种实现是正确的。代码实现// Message Routing// UVa ID: 405// Verdict: Accepted// Submission Date: 2016-08-04// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structentry{string mta,country,admd,prmd,o;};mapstring,vectorentrytables;voidrouting(entry r){setstringrouted;while(true){boolmta_foundfalse;for(autot:tables[r.mta]){boolmatchedt.countryr.country||t.country*;matchedmatched(t.admdr.admd||t.admd*);matchedmatched(t.prmdr.prmd||t.prmd*);matchedmatched(t.or.o||t.o*);if(matched){mta_foundtrue;if(routed.find(t.mta)!routed.end()){coutcircular routing detected by t.mta\n;return;}elseif(t.mtar.mta){coutdelivered to r.mta\n;return;}else{routed.insert(r.mta);r.mtat.mta;}break;}}if(mta_foundfalse){coutunable to route at r.mta\n;return;}}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intM,I,N,cases0;string mta,next_mta,country,admd,prmd,o;while(cinM){tables.clear();for(inti1;iM;i){cinmtaI;for(intj1;jI;j){cinnext_mtacountryadmdprmdo;tables[mta].push_back((entry){next_mta,country,admd,prmd,o});}}coutScenario # cases\n;cinN;for(inti1;iN;i){cinnext_mtacountryadmdprmdo;couti -- ;routing((entry){next_mta,country,admd,prmd,o});}cout\n;}return0;}