企业官网建设流程全解析

传球游戏

难度：简单

知识点：图论、度数统计、无向图

时间复杂度：O(n + m)

空间复杂度：O(n)

一、题目描述

小明正在和朋友们一起玩传球游戏。

游戏可以抽象成一个包含n个节点、m条边的无向图，每个人恰好占据一个节点。

每条边都有一个边权w，表示两个节点之间的距离。

传球需要遵守以下规则：

1. 每个人只能将球传给与自己直接相连，且距离不超过k的人。
2. 除第一个人外，每个人都不能将球传回给刚刚传球给自己的人。
3. 当某个人无法继续传球时，游戏结束。

现在，假设球最开始可以交给任意一个人，求：

• 游戏最终可能在哪些节点结束？
• 这些节点共有多少个？

输出所有可能结束游戏的节点编号，按照从小到大的顺序排列。

二、输入格式

第一行输入三个整数：

n m k

分别表示：

• n：节点数量
• m：边的数量
• k：传球的最大距离限制

接下来m行，每行输入三个整数：

u v w

表示节点u和节点v之间存在一条权值为w的无向边。

数据范围：

• 1≤n,m≤1061 \le n,m \le 10^61≤n,m≤106
• 1≤k,w≤1091 \le k,w \le 10^91≤k,w≤109
• 保证图中没有重边和自环。

三、输出格式

第一行输出一个整数，表示所有可能成为游戏终点的节点数量。

第二行按照从小到大的顺序输出这些节点的编号，编号之间用空格分隔。

四、样例

样例输入

4 3 4 1 2 3 1 3 5 2 3 4

样例输出

3 1 3 4

样例解释

由于限制k=4k=4k=4，只有边权不超过 4 的边可以传球。

因此：

• 边1 <-> 2，权值为 3，可以传球。
• 边1 <-> 3，权值为 5，不能传球。
• 边2 <-> 3，权值为 4，可以传球。
• 节点 4 没有任何边，无法传球。

筛选后的有效图如下：

1 ----- 2 ----- 3 4

此时：

• 节点 1 的有效度数为 1。
• 节点 2 的有效度数为 2。
• 节点 3 的有效度数为 1。
• 节点 4 的有效度数为 0。

节点 1 和 3 只有一个可以传球的邻居，如果球从这个邻居传过来，就无法继续传球。

节点 4 没有任何可以传球的邻居，游戏可以直接在该节点结束。

节点 2 有两个可以传球的邻居，无论从哪个邻居接球，都可以继续传给另一个邻居。

因此答案为：

1 3 4

共 3 个节点。

五、解题思路

1. 核心思想

统计每个节点的有效度数。

在无向图中，节点的度数表示与该节点相连的边的数量。

但本题有一个特殊限制：

只有边权满足

w≤k w \le kw≤k

的边才能用于传球。

因此，我们只需要统计满足条件的边所形成的图中，每个节点的度数。

定义：

deg[i] deg[i]deg[i]

表示节点i的有效度数。

2. 分类讨论

对于任意节点i，根据有效度数可以分为三种情况。

情况一：deg[i]=0deg[i]=0deg[i]=0

该节点没有任何可以传球的邻居。

如果游戏从该节点开始，就无法继续传球。

因此，该节点可以成为游戏终点。

情况二：deg[i]=1deg[i]=1deg[i]=1

该节点只有一个可以传球的邻居。

如果球从这个唯一的邻居传过来，由于不能将球传回给刚刚传球的人，因此无法继续传球。

所以，该节点也可以成为游戏终点。

情况三：deg[i]≥2deg[i]\ge 2deg[i]≥2

该节点至少有两个可以传球的邻居。

当球从某个邻居传过来时，即使不能将球传回原来的节点，仍然至少存在另一个邻居可以接球。

因此，该节点不可能成为游戏终点。

3. 得出结论

一个节点能够成为游戏终点，当且仅当：

deg[i]≤1 \boxed{deg[i]\le 1}deg[i]≤1​

因此，我们只需要：

1. 遍历所有边。
2. 如果边权w <= k，则将两个端点的有效度数加一。
3. 遍历所有节点，找出有效度数小于等于 1 的节点。
4. 按照编号从小到大的顺序输出结果。

注意：本题不需要 BFS 或 DFS，只需要统计度数即可。

六、C++ 代码（ACM 模式）

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;longlongk;cin>>n>>m>>k;// 统计每个节点的有效度数vector<int>deg(n+1,0);// 读入所有边for(inti=0;i<m;i++){intu,v;longlongw;cin>>u>>v>>w;// 只有边权不超过 k 的边才能传球if(w<=k){deg[u]++;deg[v]++;}}vector<int>ans;// 找到所有可能成为游戏终点的节点for(inti=1;i<=n;i++){if(deg[i]<=1){ans.push_back(i);}}// 输出终点数量cout<<ans.size()<<'\n';// 按照编号从小到大输出for(inti=0;i<(int)ans.size();i++){if(i>0)cout<<' ';cout<<ans[i];}cout<<'\n';return0;}

七、复杂度分析

设图中有n个节点、m条边。

时间复杂度

1. 遍历m条边，统计有效度数，时间复杂度为O(m)O(m)O(m)。
2. 遍历n个节点，筛选答案，时间复杂度为O(n)O(n)O(n)。
3. 输出答案，最坏需要O(n)O(n)O(n)的时间。

因此，总时间复杂度为：

O(n+m) \boxed{O(n+m)}O(n+m)​

空间复杂度

算法使用：

• 长度为n + 1的度数数组deg，空间复杂度为O(n)O(n)O(n)。
• 最多存储n个答案的数组ans，空间复杂度为O(n)O(n)O(n)。

因此，总空间复杂度为：

O(n) \boxed{O(n)}O(n)​

无需存储邻接表，也无需额外排序，因为我们已经按照编号从小到大遍历节点。

八、总结

这道题的关键在于将传球规则转化为图论中的度数条件。

虽然题目描述的是一个不断传球的过程，但实际上并不需要模拟过程，也不需要搜索每个起点。

只需要筛选满足w≤kw\le kw≤k的边，并统计每个节点的有效度数。

最终找出满足：

deg[i]=0或deg[i]=1 \boxed{deg[i]=0 \quad \text{或} \quad deg[i]=1}deg[i]=0或deg[i]=1​

的所有节点即可。

核心结论：

在满足边权限制的无向图中，所有有效度数不超过 1 的节点，都是可能的游戏终点。

这是一道典型的图论建模 + 度数统计题目。