作者查詢 / DJWS

總覽項目：發文 | 留言 | 暱稱

作者 DJWS 在 PTT 全部看板的留言(推文), 共1107則

限定看板：全部

看板排序：

全部Prob_Solve611C_and_CPP273Math63Soft_Job57Physics56Web_Design19Programming8Ajax7Oversea_Job4Little-Games3HatePolitics1Marginalman1Office1puzzle1Python1Tech_Job1<< 收起看板(16)

首頁

尾頁

Re: [問題] 最大流最小費用問題

[ Prob_Solve ]2 留言, 推噓總分: +1

作者: DJWS - 發表於 2015/04/03 08:51(9年前)

9^F→DJWS: 加油!04/07 06:28

Re: [問題] 最大流最小費用問題

[ Prob_Solve ]44 留言, 推噓總分: +4

作者: DJWS - 發表於 2015/03/29 10:11(9年前)

4^F→DJWS: 本來沒有反方向的邊，後來有了，也就連帶產生-cost03/29 23:16

5^F→DJWS: 他的實作方式是預先都建好反方向的邊用xor 1得到反方向的03/29 23:17

6^F→DJWS: 邊然後一開始就設定好+cost和-cost 所以他其實還是有變03/29 23:18

7^F→DJWS: 只是一開始就把所有變化預先弄好03/29 23:18

8^F→DJWS: 然後每次的最短路徑的cost也都通通不一樣03/29 23:19

18^F→DJWS: Cost' = Cost + Pi(v) - Pi(u) 這個東西就是把權重調成非負03/30 09:22

19^F→DJWS: 方便實施dijkstra最短路徑演算法03/30 09:22

20^F→DJWS: 這個技巧在CLRS的johnson's algorithm也有用過03/30 09:22

21^F→DJWS: 前面提到會有反向邊與-cost出現如果不調整成非負03/30 09:23

22^F→DJWS: 那麼只能用floyd-warshall或bellman-ford複雜度較高的方法03/30 09:24

23^F→DJWS: 然後古代的文獻基本上會把這個叫做potential什麼什麼的03/30 09:25

24^F→DJWS: 而不會介紹他有調成非負權重的功效03/30 09:25

25^F→DJWS: 這個東西是optional的你有做或沒做都不會影響正確結果03/30 09:28

26^F→DJWS: 時間複雜度差個O(V^2)而已03/30 09:29

32^F→DJWS: 我說錯了差V才對03/31 08:52

33^F→DJWS: 一開始我不知道你講的 reduced cost 是在講什麼我用猜的03/31 08:54

37^F→DJWS: 因為他一開始都沒有提到 "reduced cost" 這個詞彙04/01 09:02

[機統] 硬幣換面次數的期望值

[ Math ]4 留言, 推噓總分: 0

作者: DJWS - 發表於 2015/03/23 22:47(9年前)

4^F→DJWS: 謝謝!03/24 12:21

[問題] AAA樹？

[ Prob_Solve ]5 留言, 推噓總分: +2

作者: FRAXIS - 發表於 2015/03/07 22:26(9年前)

1^F推DJWS: http://blog.csdn.net/iamzky/article/details/4349448103/08 09:05

4^F推DJWS: 所以才有三個A?03/09 12:31

[問題] 切管問題

[ Prob_Solve ]2 留言, 推噓總分: +1

作者: lldavuull - 發表於 2015/03/07 11:19(9年前)

1^F推DJWS: bin packing problem03/08 08:58

Re: [問題] 樹上路徑和為 k

[ Prob_Solve ]2 留言, 推噓總分: +1

作者: FRAXIS - 發表於 2015/03/03 03:48(9年前)

1^F推DJWS: 謝謝! 所以沒有spine decomposition的免費教學資料?03/03 09:01

[問題] 樹上路徑和為 k

[ Prob_Solve ]12 留言, 推噓總分: +4

作者: FRAXIS - 發表於 2015/03/02 00:24(9年前)

3^F推DJWS: 能不能推薦幾篇centroid/spine decomposition的教學資料?03/02 08:14

8^F→DJWS: 路徑先從lca切兩段兩段分開處理針對一段路徑每次找樹的03/03 09:02

9^F→DJWS: 重心路徑長度只剩下不到一半所以是log級別03/03 09:02

10^F→DJWS: ^^^^^^^^不是路徑長度是剩下的節點數量03/03 09:04

11^F推DJWS: 等等 centroid decomposition如何計算一條路徑的權重?03/03 09:17

12^F→DJWS: http://www.ugrad.cs.ubc.ca/~cs490/2014W2/pdf/jason.pdf03/03 09:19

Re: [問題] 第 k 大連續子陣列和

[ Prob_Solve ]4 留言, 推噓總分: +1

作者: DJWS - 發表於 2015/02/28 08:06(9年前)

7^F→DJWS: http://ppt.cc/voTH 用FFT算兩兩和是Jeff Erickson提的03/02 08:07

8^F→DJWS: 然後算法競賽有一些相關題目用關鍵字FFT去找可以找到一些03/02 08:08

9^F→DJWS: 其他的我就不知道了我沒有追蹤論文03/02 08:09

Re: [問題] 第 k 大連續子陣列和

[ Prob_Solve ]3 留言, 推噓總分: +1

作者: DJWS - 發表於 2015/02/28 07:26(9年前)

2^F→DJWS: 對耶　爆了枉費我打那麼多字02/28 08:21

3^F→DJWS: 這樣的話也許要先想辦法找到等於零的連續和在哪些地方02/28 09:00

[問題] 第 k 大連續子陣列和

[ Prob_Solve ]11 留言, 推噓總分: +2

作者: FRAXIS - 發表於 2015/02/27 22:39(9年前)

10^F推DJWS: 1.算前綴和 2.窮舉所有連續和/平均 3.找第k大是線性時間02/28 07:08

11^F→DJWS: 抱歉我看到那是小寫了...02/28 07:09

首頁

尾頁