通过费用流中的贪心来保证计数正确性：P4249剪刀石头布
通过费用流中的贪心来保证计数正确性：P4249剪刀石头布
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135080431
https://vj.imken.moe/contest/598718#problem/K
三元环数量尽量多，也就是非三元环数量尽可能少。非三元环的充要条件是存在一个点度数为2，而每条边可以给一个点一个度数，然后就变成了经典网络流问题。
但是，对于一个点，我们还是无法求最少流。考虑转化为费用流。一个点向汇点连很多条边，分别代表着度数为1新增代价、度数为2新增代价…
显然，我们流的时候会先流费用小的，那样我们就保证了计数
的正确性。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-12-19
坐标前后限制转点的坐标取值+网络流拆维拆点：agc031_e
坐标前后限制转点的坐标取值+网络流拆维拆点：agc031_e 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135075877 https://vj.imken.moe/contest/598718#problem/J 观察到数据范围很小，但一个很重要的信息我们缺失了，就是珠宝的数量，所以我们考虑枚举珠宝的数量 kkk 。 对于横纵坐标什么至多至少的限制，比如 aia_iai 前最多偷 bib_ibi 个，可以转化为第 [bi+1,k][b_i+1,k]...
2023-12-25
网络流+先跑一遍确保正确性：ARC156F
网络流+先跑一遍确保正确性：ARC156F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135209595 https://www.luogu.com.cn/problem/AT_arc156_f 可以很显然建一个流： 然而它最大流是对的，但构造方案可能会假，因为存在最左边的边没流，相当于某个数没选。 一定有解是怎样？全选 aia_iai ，所以我们可以先全选 aia_iai 跑。然后我们再加入 bi,cib_i,c_ibi,ci 来跑，那样反悔...
2023-12-19
阴阳反转——运用INF巧妙建网络流：P3980
阴阳反转——运用INF巧妙建网络流：P3980 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135080814 https://vj.imken.moe/contest/598718#problem/L 考虑一个奇妙的转化： 有很多 inf\infinf 个人要走 nnn 扇门，第 iii 扇只能走 infa−i\inf_a-iinfa−i 个人，有 mmm 个通道，可以把一个人从 sis_isi 运到 ti+1t_i+1ti+1 ，但要给 c...
2023-10-06
充分理清限制与条件+构造二分图+最小割：ARC142E
充分理清限制与条件+构造二分图+最小割：ARC142E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133623334 https://www.luogu.com.cn/problem/AT_arc142_e 他的充要条件是是什么： ai,aj≥min(bi,bj)a_i,a_j\ge min(b_i,b_j)ai,aj≥min(bi,bj) 存在 ai≥max(bi,bj)a_i\ge max(b_i,b_j)ai≥max(bi,b...
2021-12-04
【P1230 智力大冲浪】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15643500.html 题目链接 题目 小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则： 首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数，不同的游戏扣去的...
2023-09-16
atcoder库中的网络流用法
atcoder库中的网络流用法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132643984 头文件： 12#include<atcoder/all>using namespace atcoder; 定义： 1mf_graph<int>G(N); //N为边数 连边： 1G.add_edge(u,v,w); //u->v容量为w 最大流： 1int maxflow = G.flow(S,T,1e9); //从S流向T，初始...