1. PTT
  2. NTU_EE_ALGO

[问题] 无权重树图 存在特定路径长

楼主: hschiang (hschiang)   2013-08-16 12:13:34
这题想很久了
给定一connected undirected acylic graph (i.e. tree)
所有边权重皆为1
问是否存在一个长度为k之路径
直觉的方法是穷举每个点到其他点的路径长O(N^2)
有更快的方法吗
作者: david942j (文旋)   0000-00-00 00:00:00
这是某个ACM区域赛的题目吧 分奇数偶数最长链讨论一下可以O(N) 或者是卍解用树分治+FFT更正，这不是区域赛的题目.. 原PO是在NTUJ看到的吗?
作者: david942j (文旋)   2013-09-02 14:32:00
边权都是1@@? O(N)找直径长度L 然后所有k=0~L就都存在
楼主: hschiang (hschiang)   2013-09-17 23:04:00
那假如有些是1有些是2呢
继续阅读
[闲聊] hw2 Bonusdavid942j[闲聊] hw2 bonushschiang[情报] PA3 is_spanning_tree指令shefiroth26[问题] PA3 chdir() was not declaredmhnp1580[问题] PA3 report的表格david942j[情报] PA3 DFS和BFS的输出顺序shefiroth26[情报] PA3 参考用资料结构以及vertices命名规则shefiroth26Re: [问题] PA3 输入与输出问题shefiroth26[问题] PA3 输入与输出问题david942j[情报] PA3 read_graph问题shefiroth26

Links booklink

Contact Us: admin [ a t ] ucptt.com