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]$ 向它的子区间连容量为 $...
洛谷5331 [SNOI2019]通信
LuoguLOJ分析容易想到一个费用流，即将每个哨站拆成两个点 $i$ 和 $i'$，然后源点向 $i$ 连容量为 $1$ 费用为 $0$ 的边，$i$ 向汇点连容量为 $1$ 费用为 $W$ 的边，$i'$ 向汇点连容量为 $1$ 费用为 $0$ 的边，$i$ 向 $j'$（$i<j$）连容量为 $1$ 费用为 $|a_i-a_j|$ 的边，然后求最小费用最大流即可。然而这样子边数是...
洛谷5470 [NOI2019]序列
LuoguLOJ分析至少有 $L$ 个下标相同 $\Longleftrightarrow$ 至多有 $K-L$ 个下标不同。考虑一个费用流模型，即从源点向 $a$ 中所有点连容量为 $1$、费用为 $a_i$ 的边，从 $b$ 中所有点向汇点连容量为 $1$、费用为 $b_i$ 的边，从 $a_i$ 向 $b_i$ 连容量为 $1$、费用为 $0$ 的边，再新建两个点 $C,D$，从 $C$...