当前位置：首页 > news >正文

UVa 336 A Node Too Far

news 2026/5/30 23:32:07

题目描述

为了避免网络消息（数据包）在网络中无限循环的问题，每个消息都包含一个生存时间（Time To Live, TTL\texttt{Time To Live, TTL}Time To Live, TTL）字段。该字段包含消息在被丢弃之前可以转发的节点数（站点、计算机等）。每次一个站点接收到消息时，它将TTL\texttt{TTL}TTL字段减111。如果消息的目的地就是当前站点，则忽略TTL\texttt{TTL}TTL字段的值。但如果消息必须转发，且减111后的TTL\texttt{TTL}TTL字段为000，则消息不会被转发。

在本题中，给定多个网络的描述，对于每个网络，需要确定给定初始节点和TTL\texttt{TTL}TTL值时，无法到达的节点数量。

输入格式

输入包含多个网络配置。每个网络描述以整数NCNCNC开头，表示节点之间的连接数。NC=0NC = 0NC=0表示输入数据结束。接下来NCNCNC行，每行包含两个正整数，表示连接两个节点的通信线路。任意一对节点之间最多有一条直接通信线路，每个网络的节点数不超过303030。

每个网络配置之后，有多个查询，查询格式为两个整数：起始节点编号和初始TTL\texttt{TTL}TTL设置。查询以一对0 0结束。

输出格式

对于每个查询，输出一行，显示测试用例编号（从111开始）、不可达节点数、起始节点和初始TTL\texttt{TTL}TTL值。

样例输入

16 10 15 15 20 15 55 10 50 55 40 55 60 40 20 40 50 50 60 60 65 20 25 20 30 30 47 35 30 35 40 35 50 35 2 35 3 1 1 1 2 3 2 3 3 0 0 0

样例输出

Case 1: 5 nodes not reachable from node 35 with TTL = 2. Case 2: 1 nodes not reachable from node 35 with TTL = 3. Case 3: 8 nodes not reachable from node 1 with TTL = 1. Case 4: 5 nodes not reachable from node 1 with TTL = 2. Case 5: 3 nodes not reachable from node 3 with TTL = 2. Case 6: 1 nodes not reachable from node 3 with TTL = 3.

题目分析

问题的本质

这是一个图中受限距离可达性问题。给定一个无向图，从起始节点sss出发，消息每经过一条边TTL\texttt{TTL}TTL减111。消息可以到达的节点是那些从sss出发的最短路径长度≤TTL\leq \texttt{TTL}≤TTL的节点。不可达节点包括：

最短路径长度>TTL> \texttt{TTL}>TTL的节点
图本身不可达的节点（但题目保证图连通？不保证，需考虑）

实际上，由于每条边消耗111个TTL\texttt{TTL}TTL，消息能到达的节点正是那些与sss的距离（最短路径长度）≤TTL\leq \texttt{TTL}≤TTL的节点。

因此，问题转化为：

计算所有节点之间的最短路径
对于每个查询(s,TTL)(s, \texttt{TTL})(s,TTL)，统计所有距离>TTL> \texttt{TTL}>TTL的节点数量

节点编号处理

节点编号是正整数，但可能不连续（如样例中的10,15,20,25,30,35,40,47,50,55,60,6510,15,20,25,30,35,40,47,50,55,60,6510,15,20,25,30,35,40,47,50,55,60,65）。需要进行坐标离散化，将节点编号映射到连续的1∼N1 \sim N1∼N索引，以便使用邻接矩阵。

图的大小

每个网络节点数≤30\leq 30≤30，使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法计算全源最短路径非常合适。

参考代码

// A Node Too Far// UVa ID: 336// Verdict: Accepted// Submission Date: 2016-06-26// UVa Run Time: 0.040s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intdistances[40][40];// 距离矩阵，最大 30 个节点，多预留一些空间map<int,int>indexer;// 节点编号 → 索引映射intcases=0;intn;while(cin>>n,n){// 初始化距离矩阵为无穷大for(inti=0;i<40;i++)for(intj=0;j<40;j++)distances[i][j]=100000;indexer.clear();// 读取边并离散化节点编号for(inti=1;i<=n;i++){intstart,end;cin>>start>>end;// 为未出现过的节点分配新索引if(indexer.find(start)==indexer.end())indexer[start]=indexer.size()+1;if(indexer.find(end)==indexer.end())indexer[end]=indexer.size()+1;ints=indexer[start];inte=indexer[end];distances[s][e]=1;distances[e][s]=1;}intN=indexer.size();// 实际节点数// 对角线距离为 0for(inti=1;i<=N;i++)distances[i][i]=0;// Floyd-Warshall 算法计算全源最短路径for(intk=1;k<=N;k++)for(inti=1;i<=N;i++)for(intj=1;j<=N;j++)if(distances[i][k]+distances[k][j]<distances[i][j])distances[i][j]=distances[i][k]+distances[k][j];// 处理查询intnode,ttl;while(cin>>node>>ttl,node||ttl){// 如果起始节点不在图中，则所有节点都不可达// 但题目保证起始节点一定存在于网络中ints=indexer[node];intcounter=0;for(inti=1;i<=N;i++)if(distances[s][i]>ttl)counter++;cout<<"Case "<<++cases<<": ";cout<<counter<<" nodes not reachable from node ";cout<<node<<" with TTL = "<<ttl<<"."<<endl;}}return0;}