关于第一篇题解的问题
查看原帖
关于第一篇题解的问题
241817
Chancylaser楼主2023/6/11 16:21

样例如图,假设其中标黑点是我求出的直径。

设 66 号点为直径左端点,33 号点为直径右端点。那么按照题解一的思路,求出的必经节点链的两个端点为 33 和 44,满足样例输出。

可是我一直在想一个问题,66 号节点也满足题解中的这句话:

因为还有可能出现这种情况,即dis[k]=ls[k],这样就变成了k的左边的所有边都不可能是必经边。

之所以 66 号点可以满足这个条件,是因为 66 号点没有向非直径节点连接的边,且 66 号点为直径的左端点,所以 dis[k]=0,ls[k]=0,dis[k]=0,ls[k]=0, 所以满足条件。

但是显然,66 号点不能作为我们求出的端点。

所以,为什么 66 号点不能作为我们求出的端点(即使我们知道让它作为端点是错误的)?

2023/6/11 16:21
加载中...