icontofig | 发布于 2018-12-26 10:18:42 | 阅读量 190 | 网络流 tarjan 最大流
发布于 2018-12-26 10:18:42 | 网络流 tarjan 最大流
NOI2009 植物大战僵尸(最大权闭合子图、联通量处理)
题目描述 输入格式 输出格式仅包含一个整数,表示可以获得的最大能源收入。注意,你也可以选择不进行任何攻击,这样能源收入为0。 样例输入3 2 10 0 20 0 -10 0 -5 1 0 0 100 1 2 1 100 0​样例输出25​数据范围及提示在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。一个方案为,首先进攻P1,1, P0,1,此时可以攻击P0,0 。共得到能源收益为(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,
继续阅读
icontofig | 发布于 2017-02-18 21:33:58 | 阅读量 189 | 网络流 最大流
发布于 2017-02-18 21:33:58 | 网络流 最大流
SDOI2013费用流
传送门:bzoj 3130 然后我估计这就是SDOI 喜欢出的网络流类型…… 可别被题目名称误导了,这道题不是真的费用流(对对对它是假的费用流)……这题真的只是最大流……第一问就不说了,裸的Dinic,直接一边跑就行了。至于第二问,我们注意到,由于费用是边的实际流量乘费用,所以Bob依据自己的最优策略,一定会把所有的费用都压在实际流量最大的那条边上(这是显然的)。那么作为Alice的最优策略,我们肯定是想要最大的费用最小,那么这提示够多了吧……什么?还不够?看看费用的计算方式,也就是说我们只要让最大流量的边的实际流量尽量小就行了。所以此题二分是正解……(SDOI2015也有二分网络流,这似乎是
继续阅读