wxwoo's blog

原题目链接

洛谷随机跳题跳到的

有指向，有修改，求最小：明显的最小费用最大流

我们将每个格子看成一个点，然后拆点，如下建边：

1. 源点向每个点连边，流量为1，费用为0

2. 每个点的拆点向汇点连边，流量为1，费用为0

3. 每个点向四周的点连边，流量为1，默认指向费用为0，其他为1

原题目链接

蒟蒻提供一个思路：

理论上，我们可以将

1
2
3
4
5

    ________
   |   __   |
   |  |  |  |
---------------->
   2  5  9  11

的重叠覆盖情况看成

1
2
3
4
5

    _____
   |   __|__
   |  |  |  |
---------------->
   2  5  9  11

所以，若我们将起点和终点按照从小到大的顺序排序，对答案不会产生影响

原题目链接

我们可以取两条线段的中点，若重合就让第二条线段的中点+1

$Q:$中点+1后不在线段上怎么办？

$A:$由于C++整数除法自动省略小数，也就是向下取整，若线段长度大于1，那么中点+1后一定不会超出线段，若线段长度为1，即$l+1=r$，那么$\left\lfloor\dfrac{l+r}{2}\right\rfloor=l$，所以中点$+1=r$，也不会超出线段，所以中点+1后无论如何都在线段上，符合题意

原题目链接

写这题翻译的时候，突然就有了思路

实际上这题重在思考

若a机场和b机场是同一家公司，输出0，这个很容易想到

若a机场和b机场不是同一家公司，输出1，这是为什么呢？

原题目链接

将狼和羊分成两个部分：明显的最小割

根据最大流最小割定理，最大流=最小割，所以这题可以使用最大流算法求解

我们将每个格子看成一个点，然后如下建边：

1. 源点向狼的领地连流量为$inf$的边

2. 羊的领地向汇点连流量为$inf$的边

3. 每个格子向上下左右四个格子连流量为$1$的边

原题目链接

看到题目就想到了dfs+剪枝

然后就想到了dfs有问题

例如这组数据

1
2
3

4-9-12
| | |
2-4-10

从4开始，到10结束

dfs会走$4 \to 2 \to 4 \to 10$，答案为8

然而很明显走$4 \to 9 \to 4 \to 10$更优，答案为6

当然你加一大堆玄学优化也是可以搜出正确答案的

这里不再多讲，而是提供另一种思路：

二分