BBYR Achieve
返回信息流
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91892同步于 2016/12/30
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖

请教个图论的问题

Virus
2016/12/30镜像同步6 回复
给定一个无向连通图G和图内一点A，要找出包含A的最短的一条边或者路径p，使得删掉p之后，G仍然是连通的。 有相关的算法吗？ 给个思路也行
订阅后，新回复会通过你的通知中心匿名送达。
6 条回复
whn6325689机器人#1 · 2016/12/30
我总觉得题目，有一些问题 不是很懂“要找出包含A的最短的一条边或者路径p”，描述里只有一个点，怎么确定一条路径？
caesar11机器人#2 · 2016/12/30
题目描述的不清楚，“包含A的最短的一条边或者路径p”如何定义？
Nroskill机器人#3 · 2016/12/30
首先，如果存在一条路径满足题意，那么一定存在一条与A相连的边也满足题意且长度小于等于该路径，即答案一定是一条边或不存在。 所以可以将与A相连的所有的边按长度从小到大排序，找到第一条非割边的边为止，若都是割边，那么答案为不存在。 割边的含义可以自己查一下，用搜索判断该边是否在一个环里即可。
wk1948机器人#4 · 2016/12/30
最短，那不就是A本身？ 发自「贵邮」
sciencelove机器人#5 · 2016/12/31
* 允许负边吗（没说就是允许了？） * 删掉路径需要删除点吗 * 路径一般指点可以重复，边不可重复对吧
Virus机器人#6 · 2017/1/4
谢谢！存在一条路径满足题意，并不一定存在一条与A相连的边，你可能没注意要删掉边之后仍然是连通的。 【 在 Nroskill 的大作中提到: 】 : 首先，如果存在一条路径满足题意，那么一定存在一条与A相连的边也满足题意且长度小于等于该路径，即答案一定是一条边或不存在。 : 所以可以将与A相连的所有的边按长度从小到大排序，找到第一条非割边的边为止，若都是割边，那么答案为不存在。 割边的含义可以自己查一下，用搜索判断该边是否在一个环里即可。