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