pta垃圾桶分布
时间: 2025-05-26 22:12:00 浏览: 20
### PTA系统中垃圾桶分布图实现方案
在PTA系统的垃圾箱分布问题中,目标是从给定的居民点和垃圾箱候选点之间找到最优解,使得某个垃圾箱到所有居民点的距离满足特定条件。以下是该问题的具体分析与解决方案。
#### 1. 输入解析
输入数据由三部分组成:
- 居民点数量 `n` 和垃圾箱候选点数量 `m`。
- 道路的数量 `k` 及其具体描述,每条道路通过三个参数表示:两个端点编号 `P1`, `P2` 和它们之间的距离 `Dist`[^1]。
- 给定的最大允许距离阈值 `Ds`。
这些信息构成了一个无向加权图,其中节点代表居民点和垃圾箱候选点,边则表示两点间的连接及其权重(即距离)[^3]。
#### 2. 图构建
为了处理上述数据结构,需创建一个邻接表来存储所有的顶点以及与其相连的其他顶点及对应边的权重。Python中的字典非常适合用于此目的:
```python
from collections import defaultdict, deque
def build_graph(n_plus_m, roads):
graph = defaultdict(list)
for p1, p2, dist in roads:
graph[p1].append((p2, dist))
graph[p2].append((p1, dist)) # 因为是无向图
return graph
```
这里定义了一个函数 `build_graph()` 来接收总节点数目 `n_plus_m` 和所有路径列表 `roads`,并返回完整的图表示形式。
#### 3. 最短路径计算
采用Dijkstra算法或者Floyd-Warshall算法求取任意两节点间最短路径矩阵。由于本题涉及较大规模的数据量 (`n<=1000`) ,推荐使用堆优化版 Dijkstra 方法逐个源点出发寻找至其余各点最小代价路线;而当需要频繁查询多对节点间关系时,则可考虑全枚举型 Floyd 算法简化操作流程[^2]:
##### 使用Dijkstra算法的例子如下所示:
```python
import heapq
INF = int(1e9)
def dijkstra(graph, start, n_plus_m):
distances = [INF]*(n_plus_m+1)
heap = []
distances[start]=0
heapq.heappush(heap,(distances[start],start))
while heap:
current_distance,node=heapq.heappop(heap)
if(current_distance>distances[node]):
continue
for neighbor,dist_to_neighbor in graph[node]:
distance=current_distance+dist_to_neighbor
if(distance<distances[neighbor]):
distances[neighbor]=distance
heapq.heappush(heap,(distance,neighbor))
return distances
```
对于每一个可能成为最终选定位置的垃圾桶站点i(i∈{n+1,...,n+m})分别调用一次dijkstra()得到它到达各个住户j(j∈{1,...,n})所需的最少步数数组dis[][],进而统计最大值max_dis[i]以及平均值avg_dis[i].
#### 4. 判断条件
遍历所有垃圾箱候选点 i 的 max_dis[i] 是否小于等于预设限值 Ds 。若有多个符合条件者存在,则选取具有较小 avg_dis 值的那个作为最佳选项输出相应结果;反之如果没有任何合适的位置满足约束,则打印"No Solution".
#### 结果展示样例代码片段
```python
result_index=-1
min_max_value=float('inf')
best_avg=float('inf')
for candidate_box in range(n+1,n+n_plus_m+1):
temp_distances=dijkstra(graph,candidate_box,n_plus_m)
valid=True
sum_dist=0
count_valid_residents=0
maximum_found_so_far=0
for resident_house in range(1,n+1):
d=temp_distances[resident_house]
if(d==INF or d>Ds):
valid=False
break
else:
sum_dist+=d
count_valid_residents+=1
maximum_found_so_far=max(maximum_found_so_far,d)
if(valid and ((maximum_found_so_far < min_max_value)or\
(maximum_found_so_far == min_max_value and \
float(sum_dist)/count_valid_residents < best_avg))):
result_index=candidate_box-n
min_max_value=maximum_found_so_far
best_avg=float(sum_dist)/count_valid_residents
if(result_index!=-1):
print(f"{result_index} {min_max_value:.2f} {best_avg:.2f}")
else:
print("No Solution")
```
阅读全文
相关推荐

















