【BZOJ4016】最短路径树问题 最短路+点分治

Time:.08.21

Author:xiaoyimi

转载注明出处谢谢

注意：代码中递归子树时对子树大小的计算有误,虽然可以保证正确性但是会使得求得的子树重心并不正确,可能会被卡掉

传送门

思路：

蛋疼了好久

最后还是卡线过的，成功垫底（小号跑5500ms，大号6008ms）

第一问比较好搞，spfa最短路基础上记录每个点的前驱边（这是错的，见UPD），就像费用流一样，然后重新建边就行了

第二问考虑点分治

对于每次分治部分的重心root，考虑将root作为路径上的中转点，记录数组f[x]表示之前找到的root各子树中深度为x的路径的最大值（即这条路径上有x个点）

g[x]表示当前所搜索的子树中深度为x的路径的最大值

所以查询max(f[x]+g[k-x-1])就可以了，因为还要经过root所以要减1

复杂度，我不会分析……（这也是我对点分治难以突破的瓶颈啊啊）

UPD

.10.13

感谢博友为我指出错误，当时我错误地理解了字典序的含义，真正的做法不应该是比较前驱节点的大小，而是对每个点的所有连边按另一端点的编号大小排序，然后用spfa/堆优化dij跑一遍最短路后，对整张图进行dfs，在dfs过程中只走符合最短路的边(dis[v]==dis[u]+w(u,v))，因为之前已经排过序了，所以走的过程中一定是按编号从小到大走的，每个点只会被遍历一次，这样记录下dfs过程中走过的边，这些边就是树边了。

关于连边排序的问题，用vector的朋友很容易做到，至于用数组模拟邻接表的朋友，我个人觉得可以对读入数据(u,v,w)进行排序（之前要先保证统一u＜v或u＞v），然后依次加边，也可以做到端点编号从小到大的dfs。

经过测试发现luogu和BZOJ上的数据都不会使之前那种错误方法WA（BZOJ上的新数据会使它TLE，但我把数据下载本机测试是可以AC的）。

最近比较忙，可能没时间改代码，如果大家想要对拍std什么的，可以去别的博客看看，因为写这道题的人还是挺多的，我的代码又长又常数大，就算了吧

如果觉得《【BZOJ4016】最短路径树问题 最短路+点分治》对你有帮助，请点赞、收藏，并留下你的观点哦！