1
twistoy 2018-09-04 10:03:06 +08:00 via Android
没要求加的点和边数量最小的话就很简单啊,dfs 或者 bfs 找到所有起点到终点的路径。然后都照着最长的加就可以了
|
2
PureWhiteWu 2018-09-04 10:05:12 +08:00
两次 DFS:第一次求出最长路径,第二次加电和边。
|
3
Bryan0Z OP |
4
takato 2018-09-04 10:34:38 +08:00
可以删除边吗?不然这题没有意义啊。。。
|
6
pipapa 2018-09-04 10:53:56 +08:00 via Android
bfs 若没有到达终点就一直加点和边,保证同时到达。是否可行?
|
8
ihainan 2018-09-04 11:24:34 +08:00
这种情况,如果出现环,路劲这一概念是怎么定义的…如果是按 1 - 2 - 4 和 1 - 2 - 3 - 4,那无论怎么添加都是无解呀…… |
9
yemenchun1 2018-09-04 11:26:43 +08:00
虽然不是最优解, 但是考虑下带深度限制的 dfs?
|
10
vegito2002 2018-09-04 11:39:45 +08:00
这题还是有点难的, 比如
1---2---3 | | 4----5 这种, 起点是 1, 终点是 3. 为了补全 1-2-3 这条路径的长度, 点到底加在哪里还是有点讲究: 如果加在 1-2 之间肯定不行; 更复杂一点都情况: 1---2---3---4---5 | / \ | ------6 8------ 起点是 1, 终点是 5 这种, 所有路线都没有公共前缀或者后缀, 暂时没想到一个很系统的思路. |
11
vegito2002 2018-09-04 11:43:08 +08:00
第一张图是: [1=[2], 2=[1,3,4], 3=[2,5], 4=[2,5], 5=[3,4]]
第二张图示: [1=[2,6], 2=[1,3], 3=[2,4,6,8], 4=[3,5], 5=[4,8], 6=[1,3], 8=[3,5]] V 站为什么要把所有的空格都删了... |
12
Bryan0Z OP @vegito2002 因为默认是 markdown 格式
|