企业官网建设流程全解析

题目描述

题目模拟了x.400\texttt{x.400}x.400消息处理系统中MTA\texttt{MTA}MTA（Message 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}C（Country\texttt{Country}Country，国家）
• ADMD\texttt{ADMD}ADMD（Administrative Management Domain\texttt{Administrative Management Domain}Administrative Management Domain，行政管理域）
• PRMD\texttt{PRMD}PRMD（Private Management Domain\texttt{Private Management Domain}Private Management Domain，私有管理域）
• O\texttt{O}O（Organization Name\texttt{Organization Name}Organization Name，组织名称）

每个MTA\texttt{MTA}MTA的路由表包含若干条目，每个条目指向一个相邻MTA\texttt{MTA}MTA，并包含四个组件的匹配模式。匹配模式可以是具体字符串，也可以是通配符*（匹配任意内容）。路由时，按从上到下的顺序查找第一个匹配的条目，然后将消息转发到该条目指定的MTA\texttt{MTA}MTA。

路由可能出现的三种结果：

1. 本地投递：如果匹配到的MTA\texttt{MTA}MTA就是当前MTA\texttt{MTA}MTA本身，则消息被成功投递。
2. 循环路由：如果检测到消息曾经经过同一个MTA\texttt{MTA}MTA（即形成环路），则产生循环路由错误。
3. 无法路由：如果路由表中没有任何条目匹配消息的O/R\texttt{O/R}O/R名称，则产生无法路由错误。

输入格式

每个测试场景（scenario\texttt{scenario}scenario）的输入格式如下：

• 第一行一个整数MMM（1≤M≤101 \le M \le 101≤M≤10），表示该场景中MTA\texttt{MTA}MTA的数量。
• 接下来依次描述每个MTA\texttt{MTA}MTA：
  • 一行包含MTA\texttt{MTA}MTA名称（111到101010个字母，左对齐，无空格）和整数III（0≤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描述结束后，一行包含一个整数NNN（0<N<327680 < N < 327680<N<32768），表示消息的数量。
• 接下来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_NAME
• circular routing detected by MTA_NAME
• unable 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开始，重复以下步骤：

1. 在当前MTA\texttt{MTA}MTA的路由表中，按顺序查找第一个匹配的条目。
2. 如果找不到匹配条目 →无法路由，报告当前MTA\texttt{MTA}MTA。
3. 如果找到匹配条目：
   • 如果目标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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structentry{string mta,country,admd,prmd,o;};map<string,vector<entry>>tables;voidrouting(entry r){set<string>routed;while(true){boolmta_found=false;for(autot:tables[r.mta]){boolmatched=t.country==r.country||t.country=="*";matched=matched&&(t.admd==r.admd||t.admd=="*");matched=matched&&(t.prmd==r.prmd||t.prmd=="*");matched=matched&&(t.o==r.o||t.o=="*");if(matched){mta_found=true;if(routed.find(t.mta)!=routed.end()){cout<<"circular routing detected by "<<t.mta<<'\n';return;}elseif(t.mta==r.mta){cout<<"delivered to "<<r.mta<<'\n';return;}else{routed.insert(r.mta);r.mta=t.mta;}break;}}if(mta_found==false){cout<<"unable 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,cases=0;string mta,next_mta,country,admd,prmd,o;while(cin>>M){tables.clear();for(inti=1;i<=M;i++){cin>>mta>>I;for(intj=1;j<=I;j++){cin>>next_mta>>country>>admd>>prmd>>o;tables[mta].push_back((entry){next_mta,country,admd,prmd,o});}}cout<<"Scenario # "<<++cases<<'\n';cin>>N;for(inti=1;i<=N;i++){cin>>next_mta>>country>>admd>>prmd>>o;cout<<i<<" -- ";routing((entry){next_mta,country,admd,prmd,o});}cout<<'\n';}return0;}