<span>图论 题解乱写</span>

1.Codeforce 704D

网络流题目的一个经典套路就是将两种选择变形为：

首先钦定一种选择，然后尝试替换为另一种选择。

如果有流量即为替换，否则算没替换。

所以本题直接建图，就得到了一个费用流做法。

但是本题还有一个特殊的性质，即 $r,b$ 是固定的，与每个点无关的。

所以可以直接根据 $r,b$ 的大小关系确定首先钦定的选择，然后直接跑最大流即可。

2.关于消负环

做法是这样的，把每个点拆成入点和出点。

然后将源点连每个出点 $\infty$ 边，每个入点连汇点 $\infty$ 边。

每个点的出点连向入点 $\infty$ 边，以上费用均为 $0$，再将原图中的边改为由出点连向入点即可。

然后跑最小费用最大流。

首先流满所有的源汇所连的 $\infty$ 边是可行的。

所以为了保证最大流的性质，源汇所连的 $\infty$ 边一定流满。

所以每个那么对于每一组入点和出点，假设这两个点之间流了 $k$，就是说 $out_x+k=in_x+k=\infty$，即 $out_x=in_x$。

意思就是每个点的出入度平衡，然后如果一些边能够替换一堆 $0$边，就是说出现了负环。

所以进行一些操作，就达到了消负环的效果。

因为太菜，我觉得这个消负环做法不是很行，但是值得一提的是用到的流量平衡思想。

然后对于负环的问题，其实可以用上下界网络流来解决。

考虑这样一个事情，一般的上下界网络流是钦定下界，然后去流上界-下界。

其实另一种做法是钦定上界，建反向边同样流上界-下界表示退流。

这样的话其实可以结合两种做法，只建正边权的边就可以解决这个问题。

3.chips

可能的的限制数是 $n$ 级别的，所以可以暴力枚举。

套用上面的流量平衡方法，一个想法就是建一些流量为 $1$，费用为 $1$ 的边，跑一个最大费用流，让流过这样的边来表示放上了棋子。

然后发现其实限制并不好搞，可以反转一下。

让流量为 $1$，费用为 $1$ 的边表示不放棋子。

在 $i$ 行 $i$ 列之间连流量为枚举的限制，费用为 $0$ 的边表示放上棋子。

每次判断合法然后更新答案即可。

4.离散变量（切糕）模型

因为边权为 $1$，所以最终的答案并不大。

对每个点弄一条串联的链表示最短路径的取值。 

对于一条边，给两条链加上对应的限制即可。

5.Codeforce 720 A

霍尔定理

对两个点内部的信息分别排序，然后最劣的情况一定出现在二者分别选择一段前缀。

另一种做法是考虑首先确定一些最劣情况下出现的椅子集合，然后选择能生成这样椅子集合的最坏的人的集合。

6.ARC076 F

这个时候考虑人的集合并不容易处理了。

所以考虑最劣情况下椅子的集合。

一定是一段前缀和一段后缀的并，即 $[1,l],[r,m]$ 

然后考虑怎样的人是被覆盖在这个集合中的，即所有满足 $L_i \leq l,R_i \geq r$ 的人。

这是一个二维数点问题，扫描线然后用线段树维护一下就行了。

7.删两条以内边使得图不联通

8.noi2017 游戏

9.bzoj 4152