UVa 335 Processing MX Records

题目描述域名系统DNS\texttt{DNS}DNS的主要功能是将符号化机器名如bigone.stateu.edu映射到对应的网络地址如24.99.100.33。机器名的各个部分由点分隔从右向左读取时对应树中的节点。内部节点对应域domain\texttt{domain}domain。例如.edu域下是所有美国大学和学院的机器而加拿大的所有机器都在.ca域下。通过提供一个或多个MX\texttt{MX}MX记录系统管理员可以安排DNS\texttt{DNS}DNS将发往一台机器的邮件重定向到另一台机器。重定向在许多情况下是合适的其中一个常见用途是为虚构的、具有有意义名称的机器创建邮件地址。例如允许邮件发送到info.stateu.edu但校园内并没有名为info的物理机器。通过使用适当的MX\texttt{MX}MX记录可以将邮件重定向到bigone.stateu.edu。在本题中我们将处理简化版的MX\texttt{MX}MX记录。MX 记录格式一个MX\texttt{MX}MX记录包含三个字段由空白字符分隔第一字段源机器名目标邮件地址的机器名第二字段偏好值非负整数数值越小优先级越高第三字段目标机器名邮件实际投递的目标如果第一字段不存在即行首为空格则假定它与前一行的第一字段相同。通配符记录通配符MX\texttt{MX}MX记录允许使用一条记录将邮件重定向到多台机器。例如*.citycc.midville.edu 0 tiny.stateu.edu将任何以.citycc.midville.edu结尾的机器名的邮件重定向到tiny.stateu.edu。简化假设通配符*只出现在符号名的第一部分且任何符号名中不会出现超过三个点。命令在NNN条MX\texttt{MX}MX记录之后输入包含以下命令U machine机器上线up\texttt{up}upD machine机器下线down\texttt{down}downA machine查询邮件重定向目标X输入结束所有机器初始为上线状态。注意MX\texttt{MX}MX记录不会被递归处理。即如果first.com的邮件被重定向到second.com任何可能将second.com重定向到其他机器的MX\texttt{MX}MX记录都不会在处理first.com时被检查。输入格式第一行包含整数NNN接下来NNN行每行一个MX\texttt{MX}MX记录。剩余行每行以U、D、A或X开头。输出格式对于每个A命令输出一行machine destination如果没有适用的MX\texttt{MX}MX记录输出machine 样例输入5 service.stateu.edu 10 tiny.stateu.edu info.stateu.edu 0 bigone.stateu.edu 10 tiny.stateu.edu service.stateu.edu 5 bigone.stateu.edu *.smallu.edu 10 service.stateu.edu A alpha.cs.smallu.edu A info.stateu.edu D bigone.stateu.edu A info.stateu.edu A nowhere.com X样例输出alpha.cs.smallu.edu service.stateu.edu info.stateu.edu bigone.stateu.edu info.stateu.edu tiny.stateu.edu nowhere.com 题目分析问题的本质这是一个字符串匹配 优先级选择问题。给定一组MX\texttt{MX}MX记录每条记录包含源模式完整域名或通配符模式优先级数值越小优先级越高目标机器当查询一个机器名时需要找到所有匹配该机器名的MX\texttt{MX}MX记录选择优先级最高数值最小且目标机器为上线状态的记录输出目标机器名如果没有匹配则不输出目标匹配规则精确匹配源模式与机器名完全相同通配符匹配源模式形如*.domain匹配所有以.domain结尾的机器名匹配优先级在相同优先级下精确匹配优先于通配符匹配题目没有明确说明但从样例可知需要取所有匹配记录中优先级最高的如果优先级相同取哪个题目没有要求只需输出一个即可。机器状态初始所有机器为上线up\texttt{up}upU machine将机器设为上线D machine将机器设为下线只有上线的目标机器才能被选为最终目的地。参考代码// Processing MX Records// UVa ID: 335// Verdict: Accepted// Submission Date: 2016-07-07// UVa Run Time: 0.170s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 机器状态true在线false离线mapstring,boolstatus;// MX 记录索引仅用于记录实际未使用mapstring,intindexer;// MX 记录存储源模式 - (优先级, 目标) 的多重映射mapstring,multimapint,stringrecords;// 判断机器是否在线已注册且状态为 trueinlineboolisMachineLive(string machine){return(status.find(machine)!status.end()status[machine]);}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intn,second_field;string line,last_first_field,first_field,third_field,machine;istringstream iss;// 读取 MX 记录数量getline(cin,line);nstoi(line);// 读取并存储所有 MX 记录for(inti1;in;i){getline(cin,line);iss.clear();iss.str(line);// 判断第一字段是否存在行首是否有空格if(line.front()! ){issfirst_fieldsecond_fieldthird_field;last_first_fieldfirst_field;}else{isssecond_fieldthird_field;first_fieldlast_first_field;}// 存储记录records[first_field].insert(make_pair(second_field,third_field));indexer[first_field]i;// 初始化机器状态为在线status[first_field]true;status[third_field]true;}charaction;while(getline(cin,line),line.front()!X){iss.clear();iss.str(line);issactionmachine;if(actionU||actionD){// 更新机器状态if(status.find(machine)!status.end())status[machine](actionU);// 通配符模式的状态更新elseif(status.find(*.machine)!status.end())status[*.machine](actionU);}elseif(actionA){coutmachine ;boolflagfalse;intminPreference;string destination;// 1. 精确匹配for(autorecord:records[machine]){if(isMachineLive(record.second)){minPreferencerecord.first;destinationrecord.second;flagtrue;break;// 由于 map 按优先级升序存储第一个即为最优}}// 2. 通配符匹配逐级检查for(intstartmachine.find(.,0);start!string::npos;start1,startmachine.find(.,start)){string next_machine*machine.substr(start);for(autorecord:records[next_machine]){if(isMachineLive(record.second)){if(!flag){minPreferencerecord.first;destinationrecord.second;flagtrue;}elseif(record.firstminPreference){minPreferencerecord.first;destinationrecord.second;}}}}if(flag)cout destination;coutendl;}}return0;}