※ 引述《Favonia (00010110110001101010100)》之銘言： : ※ 引述《AcmeChimera (The Agent of God)》之銘言： : : 不懂耶 可以請你講清楚一點嗎? : 1. 首先給個 s,t 然後所有礦坑是一個點 xi : 2. 如果要先挖礦坑 i 才能挖礦坑 j 則 cap(xj->xi)=inf : 3. 如果礦坑 i 是賺 a 圓，cap(s->xi)=a : 如果礦坑 i 是虧 a 圓，cap(xi->t)=a : 4. 其他 cap = 0 我的方法跟你差不多 1. 建立兩個頂點 s,t 2. 對每個礦坑i, 如果 cost > 0 , 建立一條 (s->i) cap=cost的邊 如果 cost < 0 , 建立一條 (i->t) cap=-cost的邊 3. 對每個依賴性的關係 (i,j) 表示在挖 i 前 必須先挖 j 再度建立一個 (i->j) cost=inf的邊 4. Run Maxflow 5. 最大值就是所有正整數的總合-MaxFlow的值 6. 要找出最佳解的集合, 從s作DFS,所拜訪到頂點,即是要求的最佳解 -- ps. 這個問題沒有考慮到cost=0的情形, 我想題目也沒說清楚 ... 這個方法經過昨天Contest執行無誤...應該是沒錯吧 :Q ps2. 我們被屠殺了 Orz.. (揮手再見) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.115.17.19