题意分析

题目要求模拟一个简化的MBone（多播骨干网）网络。MBone是一种构建在IP协议之上的虚拟网络，支持多播通信。主要组成部分包括：

1. 岛屿（Island）：由多播路由器和其所属主机组成
2. 隧道（Tunnel）：连接不同路由器的通信通道
3. 多播组（Multicast Group）：主机可以加入/离开的通信组

关键规则：

• 主机通过向路由器发送协议消息加入组
• 发送数据包时，路由器会复制包并通过所有隧道转发
• 每个包有TTL（生存时间），通过隧道时会减少
• 主机只保留TTL最大的包副本

解题思路

1. 数据结构设计：

   • 使用结构体表示路由器和数据包
   • 用map维护主机-路由器映射和组成员关系

2. 网络拓扑构建：

   • 读取输入并建立路由器、主机和隧道的关系

3. 活动模拟：

   • 处理加入/离开组的请求
   • 使用BFS模拟数据包传播：
     • 检查TTL是否足够通过隧道
     • 记录传播路径避免循环
     • 更新主机收到的最佳TTL包

4. 结果处理：

   • 按要求的格式排序输出结果
   • 确保输出格式正确

正确代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;

struct Island {
    string router_name;
    map<int, set<int>> host_groups; // host -> groups
    vector<pair<int, string>> tunnels; // threshold, target
};

struct Packet {
    int id;
    int ttl;
    int group;
    string path;
};

struct ReceivedPacket {
    int host;
    int packet_id;
    int ttl;
    
    bool operator<(const ReceivedPacket& other) const {
        if (host != other.host) return host < other.host;
        return packet_id < other.packet_id;
    }
};

vector<Island> islands;
map<string, int> router_to_index;
map<int, string> host_to_router;
set<ReceivedPacket> received_packets;

void process_join(int host, int group) {
    string router = host_to_router[host];
    int idx = router_to_index[router];
    islands[idx].host_groups[host].insert(group);
}

void process_leave(int host, int group) {
    string router = host_to_router[host];
    int idx = router_to_index[router];
    islands[idx].host_groups[host].erase(group);
}

void process_send(int host, int group, int packet_id, int ttl) {
    string router = host_to_router[host];
    queue<pair<int, Packet>> q; // island index, packet
    Packet p = {packet_id, ttl, group, router};
    q.push({router_to_index[router], p});
    
    set<pair<int, string>> visited; // island index, path
    
    while (!q.empty()) {
        auto current = q.front();
        q.pop();
        int island_idx = current.first;
        Packet packet = current.second;
        
        // Deliver to local hosts
        for (auto& [h, groups] : islands[island_idx].host_groups) {
            if (groups.count(packet.group)) {
                received_packets.insert({h, packet.id, packet.ttl});
            }
        }
        
        // Forward through tunnels
        for (auto& [threshold, target] : islands[island_idx].tunnels) {
            if (packet.ttl >= threshold) {
                string new_path = packet.path + "->" + target;
                if (visited.count({router_to_index[target], new_path})) continue;
                
                visited.insert({router_to_index[target], new_path});
                Packet new_packet = packet;
                new_packet.ttl -= threshold;
                new_packet.path = new_path;
                q.push({router_to_index[target], new_packet});
            }
        }
    }
}

int main() {
    int network_num = 1;
    while (true) {
        int m;
        cin >> m;
        if (m == 0) break;
        
        // Clear previous data
        islands.clear();
        router_to_index.clear();
        host_to_router.clear();
        received_packets.clear();
        
        // Read network topology
        for (int i = 0; i < m; ++i) {
            string router_name;
            int num_lines;
            cin >> router_name >> num_lines;
            
            Island island;
            island.router_name = router_name;
            router_to_index[router_name] = i;
            
            for (int j = 0; j < num_lines; ++j) {
                char type;
                cin >> type;
                if (type == 'H') {
                    int host_addr;
                    cin >> host_addr;
                    host_to_router[host_addr] = router_name;
                } else if (type == 'T') {
                    int threshold;
                    string target;
                    cin >> threshold >> target;
                    island.tunnels.emplace_back(threshold, target);
                }
            }
            islands.push_back(island);
        }
        
        // Read activities
        int num_activities;
        cin >> num_activities;
        for (int i = 0; i < num_activities; ++i) {
            char activity;
            cin >> activity;
            if (activity == 'J') {
                int host, group;
                cin >> host >> group;
                process_join(host, group);
            } else if (activity == 'L') {
                int host, group;
                cin >> host >> group;
                process_leave(host, group);
            } else if (activity == 'S') {
                int host, group, packet_id, ttl;
                cin >> host >> group >> packet_id >> ttl;
                process_send(host, group, packet_id, ttl);
            }
        }
        
        // Output results
        cout << "Network #" << network_num++ << endl;
        for (const auto& pkt : received_packets) {
            cout << pkt.host << " " << pkt.packet_id << " " << pkt.ttl << endl;
        }
        cout << endl;
    }
    return 0;
}