※ 引述《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