UVa 593 MBone

题目描述题目模拟了一个多播网络。网络由多个岛屿组成每个岛屿有一个多播路由器和若干主机。路由器之间通过隧道连接每个隧道有一个阈值。主机可以加入或离开多播组也可以发送数据包到某个组。数据包有TTL\texttt{TTL}TTLTime To Live\texttt{Time To Live}Time To Live每经过一个隧道TTL\texttt{TTL}TTL减去该隧道的阈值。当TTL\texttt{TTL}TTL 隧道阈值时数据包不会通过该隧道。主机收到数据包时只保留TTL\texttt{TTL}TTL最大的那个若相同则保留先收到的题目要求只保留TTL\texttt{TTL}TTL最高的。输出每个主机收到的数据包按主机地址升序再按数据包ID\texttt{ID}ID升序。输入格式输入包含多个网络描述。每个网络第一部分描述拓扑第一行整数mmm1≤m≤101 \le m \le 101≤m≤10表示岛屿数。接下来mmm个岛屿描述每行路由器名称和行数ddd接下来ddd行每行以H主机地址或T隧道阈值 目标路由器名开头。第一部分结束后第二行一个整数aaa表示活动数。接下来aaa行每行一个活动J 主机地址 组地址加入、L 主机地址 组地址离开、S 主机地址 组地址 数据包ID TTL发送。输入以m0m 0m0结束。输出格式对于每个网络输出Network #X然后每行输出主机地址 数据包ID TTL按主机地址升序、数据包ID\texttt{ID}ID升序排列。每个网络输出后跟一个空行。样例输入3 Nuremberg 3 T 8 Munich H 3768 H 3669 Munich 6 H 721 H 722 H 723 T 6 Nuremberg H 857 T 9 Ulm Ulm 5 H 51225 H 51226 H 51227 T 15 Nuremberg T 9 Munich 14 J 51227 26 J 3768 27 J 723 26 J 3768 26 S 3768 26 1000 17 J 857 26 S 3768 26 320 16 J 722 26 L 857 26 S 51227 26 1001 37 S 723 26 533 5 L 51227 26 L 3768 27 L 723 26 0输出Network #1 722 533 5 722 1001 28 723 320 8 723 533 5 723 1000 9 723 1001 28 857 320 8 3768 320 16 3768 1000 17 3768 1001 22 51227 1000 0 51227 1001 37题目分析本题的核心是计算路由器之间的最短路径距离为阈值之和然后对于每个数据包计算它能到达哪些主机。算法构建有向图节点为路由器边权为隧道阈值。使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall计算所有路由器对之间的最短路径即最小阈值和。对于每个发送事件遍历当前组中的所有主机检查从源主机所在路由器到目标主机所在路由器的距离是否≤\le≤数据包的TTL\texttt{TTL}TTL。若是则主机收到数据包剩余TTL\texttt{TTL}TTL 原始TTL\texttt{TTL}TTL- 距离。同一主机收到同一数据包的多个副本时只保留剩余TTL\texttt{TTL}TTL最大的。使用映射packetReceived[host]存储(packetId, ttl)对并保持最大TTL\texttt{TTL}TTL。复杂度分析路由器数≤10\le 10≤10Floyd-WarshallO(103)O(10^3)O(103)。活动数≤1000\le 1000≤1000每个发送事件遍历组内主机最多505050可接受。代码实现// MBone// UVa ID: 593// Verdict: Accepted// Submission Date: 2017-05-14// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;boolcmp(pairint,inta,pairint,intb){returna.firstb.first;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intislands,cases0;while(cinislands,islands){mapstring,intindexer;mapint,inthostInRouter;mapint,setintgroups;mapint,vectorpairint,intpacketReceived;charkinds;introuterId0,datalines,activities;intcost,hostId,groupId,packetId,ttl;string source,dest;intdist[20][20],INF1000000;for(inti0;iislands;i){for(intj0;jislands;j)dist[i][j]INF;dist[i][i]0;}for(intc1;cislands;c){cinsourcedatalines;if(indexer.find(source)indexer.end())indexer[source]routerId;for(intd1;ddatalines;d){cinkinds;if(kindsT){cincostdest;if(indexer.find(dest)indexer.end())indexer[dest]routerId;dist[indexer[source]][indexer[dest]]cost;}else{cinhostId;hostInRouter[hostId]indexer[source];}}}for(intk0;kislands;k)for(inti0;iislands;i)for(intj0;jislands;j){intthroughdist[i][k]dist[k][j];if(dist[i][j]through)dist[i][j]through;}cinactivities;for(intc1;cactivities;c){cinkinds;if(kindsJ){cinhostIdgroupId;groups[groupId].insert(hostId);}elseif(kindsL){cinhostIdgroupId;groups[groupId].erase(hostId);}else{cinhostIdgroupIdpacketIdttl;for(autohost:groups[groupId]){intfromhostInRouter[hostId],tohostInRouter[host];if(ttldist[from][to])packetReceived[host].push_back(make_pair(packetId,ttl-dist[from][to]));}}}coutNetwork #cases\n;for(autopacket:packetReceived){sort(packet.second.begin(),packet.second.end(),cmp);for(autodata:packet.second)coutpacket.first data.first data.second\n;}cout\n;}return0;}