BZOJ3218 a + b Problem
BZOJ分析容易看出最小割。考虑连边：对于每个方格，从 $s$ 向它连容量为 $b_i$ 的边，从它向 $t$ 连容量为 $w_i$ 的边。对于每个方格，新建一个节点 $i'$，从 $i$ 向 $i'$ 连容量为 $p_i$ 的边，从 $i'$ 向 $a_j\in [l_i,r_i]$ 且 $j<i$ 的方格 $j$ 连容量为 $+\infty$ 的边。考虑正确性：显然对于每个方格，$...
标签 网络流 下的文章
- 首页
- 网络流
51nod1325 两棵树的问题
51nod分析考虑钦定一个点一定在选出的子集中。我们把钦定的这个点作为根，那么如果 $x$ 在子集中，则 $x$ 在两棵树上的父节点都应该在子集中。那么问题就转化成了最大权闭合子图，直接网络流即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ /...
洛谷5769 [JSOI2016]飞机调度
Luogu分析预处理出一个 $dis_{i,j}$ 表示从 $i$ 起飞到 $j$ 并能再次起飞的最短时间。将 $T_{i,j}+p_j$ 作为 $dis_{i,j}$ 的初始值然后 Floyd 即可。那么如果 $d_i+t_{x_i,y_i}+p_{y_i}+dis_{y_i,x_j}\leq d_j$ ，说明 $i$ 航线的飞机能给 $j$ 航线用。考虑建立一个图论模型。如果 $i$ 航...
洛谷4043 [AHOI2014/JSOI2014]支线剧情
Luogu分析题目很像路径覆盖，因此可以考虑网络流。令 $1$ 号点为源点，再新建一个汇点，然后连边：如果 $u$ 能到 $v$，从 $u$ 向 $v$ 连一条下界为 $1$，上界为 $+\infty$，费用为 $t$ 的边，表示至少要看一次这段剧情，看一次需要花 $t$ 的时间。所有点向汇点连一条下界为 $0$，上界为 $+\infty$，费用为 $0$ 的边。然后求有源汇有上下界最小费用...
洛谷5038 [SCOI2012]奇怪的游戏
Luogu分析首先对整个图黑白染色。设 $cb$ 表示黑点的数量，$sb$ 表示黑点的权值和，$cw$ 表示白点的数量，$sw$ 表示白点的权值和。再设所有数最终变为 $x$，则可以列出方程这时需要分类讨论一波：当 $cb\neq cw$ 时，我们可以直接解出 $x$，只需要判定解出的 $x$ 能否合法即可。当 $cb=cw$ 时，可以发现答案满足可二分性，因此我们可以二分答案。问题最终归结...
LOJ526 「LibreOJ β Round #4」子集
LOJ分析这个题比较有意思。一个简单的想法是每对合法的 $i,j$ 之间连一条边，那么我们相当于要求最大团。直接求最大团肯定是求不出的。注意到最大团等于补图的最大独立集，因此我们考虑这个图的补图会不会有什么特殊的性质。可以发现，如果 $a_i,a_j$ 奇偶性相同，那么 $i,j$ 间一定有一条边。因此在补图中，任意奇数间不会有连边，任意偶数间也不会有连边。也就是说，补图是一个二分图！那么求...
CF343E Pumping Stations
CodeforcesLuogu分析显然先把最小割树建出来。首先有一个结论：第一问答案的上界为最小割树上所有边权之和。下面考虑怎样达到这个上界。考虑最小割树上的最小边，我们应让它只被经过一次。设它的两个端点为 $a_i,a_{i+1}$ ，则 $a_{1..i-1}$ 中任意两点不经过该边，$a_{i+2..n}$ 中任意两点不经过该边。于是将该边断掉后两边递归处理即可。代码// ======...
CF510E Fox And Dinner
CodeforcesLuogu分析显然每个环一定是奇偶相邻的。考虑这样的网络流模型：源点向每个偶数连容量为 $2$ 的边，代表可以和两个奇数相邻。每个奇数向汇点连容量为 $2$ 的边，意义和上面类似。对于一个偶数 $u$ 和一个奇数 $v$ ，如果 $u+v$ 是质数，那么从 $u$ 向 $v$ 连容量为 $1$ 的边，代表两个数可以相邻。然后跑最大流，如果最大流 $\neq n$ 就无解。...
洛谷4249 [WC2007]剪刀石头布
Luogu给竞赛图中一些边定向，使得三元环数目最大。分析神仙网络流题...首先三元环个数不是很好算，考虑用总数减去不是三元环的。总数显然是考虑三个点要怎样才不会构成三元环，可以发现有一个点的入度为 $2$ 即可。进一步发现，如果 $u$ 的入度为 $d$ ，那么整张图会产生 $d\choose 2$ 个不是三元环的三元组。考虑差分。对于一个点 $u$ ，如果它的入度增加了 $1$ 变成了 $...
洛谷4123 [CQOI2016]不同的最小割
LuoguLOJ分析首先建出最小割树。因为两点间的最小割就是在最小割树路径上边权的最小值，分析一下可以得到答案就是最小割树上不同的边权数。于是直接拿一个 set 维护一下所有边权即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =====...