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