第一问没什么好说的。直接看第二问。 一个很直接的想法就是,在每条边上都加上一条容量为\(k\),费用为\(c_ …
lp2766 网络流24题-最长不下降子序列问题
这是一道看起来很简单的麻题。 很显然可以发现第一问就是直接n^2DP求一个答案。 第二问模拟寻找最长不下降子序 …
lp2764 网络流24题-最小路径覆盖问题
(其实建图方法已经写在题目里了。) (这一题是一道匈牙利的裸题,考场上二分图最大匹配仍然建议使用匈牙利(因为在 …
lp2763 网络流24题-试题库问题
对于这一题,我们建三层的边来描述题目中的约束。 对于每道题建一个点,源点连一条容量为1的边到每一个点,表示每道 …
lp5030 长脖子鹿放置
观察这一题的攻击方式,我们可以发现一个特点——所有奇数行的长颈鹿都攻击不到偶数行的长颈鹿,反之亦然。 所以,我 …
lp3355 网络流24题-骑士共存问题
首先我们观察这道题。 暴力地状压DP或者之类的操作显然会MLE/TLE。 我们发现,横坐标和纵坐标相加的和的奇 …
lp2756 网络流24题-飞行员配对方案问题
这是一个裸的配对问题。 我们可以建成一个二分图然后跑匈牙利。
lp3376 【模板】网络最大流
全机房就我一个还不会网络流了。 下面我整理一下网络流的基本概念,辅助自己理解。 首先关于网络流的定义。形式化地 …