pku3336 判断点在线段上
评论34次阅读2008.09.15 21:20; 作者：Felicia
题目数据范围有误。应该是(1 ≤ n ≤ 100, 1 ≤ m ≤ 3000)
我的做法是
- 对于每个police，判断他在几条路上。这样可以区分开路口police和路中police
- 按所有的路中police把路分成更小的路，称之为小路
- 枚举每对小路，判断他们是否可以直接互相到达
- 找出start, end所在的小路
- 用并查集把所有能互相到达的小路合并，然后看看start, end所在的小路是否在同一集合中
发表回复
- 评论 (0)
- 引用通告 (0)
发表评论 引用通告暂无评论.
暂无引用通告