还是网络流
1. 早读
P2254 [NOI2005] 瑰丽华尔兹
吾有感而发，遂小说
看背景 [ ? 喔看过呱 ]
读题中 [ 嘶 ~ ， 看着有点难 ， 最长路径还得满足顺序 ]
看范围 [ 我去，我每一步暴力 \(dp\) 都能拿好多分 ， 先写暴力吧 ]
写一半 [ 这个 \(k\) 段咋没用 ？ 喔去，那我每次更新一段不行吗？，喔喔喔喔 ... 好像过了 ]
没错，然后听 \(qk\) 说暴力可过，满心欢喜地交了一发 TLE 70pt
me : 骗我啊啊啊啊啊啊啊啊啊啊啊
qk ： 不管，反正我的暴力过了
me ：那是你的问题 qwq
然后写了正解，也不好写，因为要写 4 份类似的 \(dp\)
修修补补过了漾礼，交上去 50 pt
发现是 0 的状态把别的状态单调了 T_T
码
2.
P6054 [RC-02] 开门大吉
开门大只因
可以先把那个人做那套题期望算出来
然后切糕问题没了
复习了一下切糕
切糕模型自带每条链选一个（ 可以自己流一下
然后这个还不太一样
就是限制多出去的那当前情况非法
举个例子就是你要求 \(1 <= a，b <= 5\)
要求 \(a >= b + 2\)
那 \(b\) 取 \(4\) 时就非法，因为 \(4 + 2 > 5\)
这样可以把对应边流量改为 \(inf\) 或直接连一条 到 \(t\) 流量 \(+ inf\) 的边
还要注意就是这题是少见的 double
别的都一样，精度别太高就行，不然 TLE
码
3.
P2765 魔术球问题
发现是最小路径覆盖
最小路径覆盖 = 点数 - 最大匹配
证明就是考虑刚开始每个点一条路径 ， 匹配一对说明路径少 \(1\)
码
4.
P4177 [CEOI 2008] order
[ 这玩意啥呀 ， 又买又租的 ]
[ 肯定工作一排，机器一排，先摆阵 ]
[ 那我按费用花费连上，中间连上 \(inf\) 不对，那对应边权呢，那我连对应边权 ]
[ 欸嘿，这么连 ？ 好像还挺对 ]
[ 喔去 ， 那这不是模板吗 ？ ]
码
5.
P3973 [TJOI2015] 线性代数
[ 这玩意啥呀，这能是网络流？ ]
[ 我先模一下 ]
[ 像线性规划... ]
相关新闻
