洛谷6621 [省选联考 2020 A 卷]魔法商店
LuoguLOJ分析根据拟阵的相关理论可以知道：$A$ 是权值最小的基当且仅当 $\forall u\in A,v\notin A$，只要 $(A\backslash\{u\})\cup\{v\}$ 是基，则 $v_u\leq v_v$；权值最大的基的情况同理。这样子就把原题中最小值、最大值的限制转化成了若干组偏序关系。现在的问题即为 $p=2$ 时的保序回归问题。根据论文中的理论，考虑整体...
标签 网络流 下的文章
- 首页
- 网络流
洛谷6967 [NEERC2016]Delight for a Cat
LuoguGym分析考虑线性规划。设 $x_i$ 为第 $i$ 小时是否吃饭，可以列出线性规划用 NOI2008 志愿者招募 一题的方法建图求最大费用最大流即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==============...
AtCoder Regular Contest 074 简要题解
比赛地址Chocolate Bar横着竖着是一样的，这里只考虑横着。那么要么是横切三刀，要么是先横切一刀再竖切一刀。前面只要看 $H$ 是不是 $3$ 的倍数，不是的话差最小是 $W$。后面可以直接枚举横切在哪，竖切一定切在 $\frac{W}{2}$ 的位置。代码3N Numbers显然存在一个分界线 $i\in[n,2n]$，满足在 $[1,i]$ 中选了最大的 $n$ 个、在 $[i+...
POI2011 简要题解
Conspiracy考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。可能会有些卡空间。代码Lollipop可以发现如果存在一段和为 $w$，则一定存在一段和为 $w-2$，...
洛谷3511 [POI2010]MOS-Bridges
LuoguLOJ分析考虑二分答案，则我们需要判定是否存在混合图欧拉回路。首先混合图不连通的话一定不存在。然后给无向边任意定向，算出每个点的度数，如果有点度数为奇数则不存在。那么对于一条无向边，假设我们定向 $u\to v$，则我们可以改变它的方向使得 $in_u-out_u$ 增加 $2$、$in_v-out_v$ 减少 $2$。因此可以考虑网络流。对于 $in_ out_i$ 的点，从源点...
洛谷5996 [PA2014]Muzeum
Luogu分析不难看出一个最大权闭合子图的模型，然而直接求最大流显然过不了，于是可以考虑模拟最大流。首先把这个坐标系变换一下。如果警卫 $a$ 能看到手办 $b$，则应有于是可以把 $(h\times x+w\times y,h\times x-w\times y)$ 作为每个点的坐标，这样子警卫 $a$ 能看到手办 $b$ 当且仅当 $x_b\leq x_a,y_a\leq y_b$。考虑...
CF1354F Summoning Minions
CodeforcesLuogu分析有几个比较显然的结论（证明不会）：一定存在一组最优解，使得所有卡都被摆上去过。感性理解：因为 $b_i\geq 0$ 所以你就算摆上去再拿下来也不会更差。一定存在一组最优解，满足首先摆上 $k-1$ 张卡，再将 $n-k$ 张卡摆上去后立即拿下来，再将剩下的那张卡摆上去。感性理解：此时 $b_i$ 的贡献是最大的，且 $a_i$ 的贡献没有影响。那么相当于要...
LOJ6045 「雅礼集训 2017 Day8」价
LOJCF 原题分析感觉很像最小权闭合子图。为了方便把所有费用取负。考虑这样的连边方式源点向每种药连容量为 $+\infty+p_i$ 的边。每种药向所需的药材连容量为 $+\infty$ 的边。每种药材向汇点连容量为 $+\infty$ 的边。拿最小割减去所有 $+\infty+p_i$ 的和即为答案（因为取了负）。下面是正确性理解：首先可以发现，第二种的边是不会割的，如果割了换成第三种边...
LOJ6068 「2017 山东一轮集训 Day4」棋盘
LOJ分析考虑二分图。对于每一行、列被 # 隔开的每一段拿出来当做一个点，然后对于每个点从其所属的行连通块向列连通块连边。但是每个连通块内可以放多个棋子。假设一个连通块内放了 $x$ 个棋子，那么会产生 $\frac{x(x-1)}{2}$ 的费用，我们要最小化费用。考虑费用递增。由于 $\frac{(x+1)x}{2}-\frac{x(x-1)}{2}=x$，所以我们只需要连若干条容量为 ...
洛谷3749 [六省联考2017]寿司餐厅
LuoguLOJ分析数组开小 -> 100->40 -> 身败名裂先考虑没有费用的情况，显然是最大权闭合子图模型（选了 $[i,j]$ 就必须选它的所有子区间）。因此对于每个 $[i,j]$，如果 $d_{i,j}$ 为正则从源点向它连容量为 $d_{i,j}$ 的边，否则从它向汇点连容量为 $-d_{i,j}$ 的边，然后对于每个 $[i,j]$ 向它的子区间连容量为 $...