Tag Archives

11 Articles

OI

Codeforces 704D:Captain America – 题解

Posted by kal0rona on

主要思路

一道比较板的上下界网络流。先考虑 \( red > blue \) 的情况,我们把所有点染成红色的然后再做个最大替换即可。我们考虑对每个点、每个横坐标、每个纵坐标做一个点,横坐标和源点、纵坐标和汇点的边需要大概算一下,得出流量范围 \(\frac{cnt_x}{2} \leq flow \leq \frac{d + cnt_x}{2}\)。得出这个范围之后就用板子套一下即可。

OI

雅礼集训 2018 Jan 2nd – 解题报告

Posted by kal0rona on

A – 串

如果本身就不是回文串,那么答案就是 \(1\);如果本身是的话,考虑找一个分割点使得左右都不是,那么答案就是 \(2\);如果还是没找到,那么就是无解了,因为最后串要么就是个单纯串或者是个删完一次之后变成单纯串的东西。

OI

[Fortuna OJ]4682「GDOI2017模拟8.11」生物学家

Posted by kal0rona on

主要思路

这道题原题解作者的思路非常的清晰。我来阐述一下。

首先思考答案的意义,一定是总的权值和减去:

  • 变性花费
  • 不要的赞助费
  • 喝茶费用

我们可以用上面这三个元素组一个网络流,计算最小割使答案最大。

考虑将源点连入雌性,雄性连入雄性,流上限就是变性花费:如果将这种边割掉,那么就是不需要进行变性。考虑朋友的边,如果倾向于变雌性,源点连入,向所有的对应编号连边;如果雄性,连入汇点,所有对应编号的向该朋友连边。

OI

网络流

Posted by kal0rona on
网络流

From wallpaperhub.app

定义

在有向图中,有唯一的源地(入度为 0)和汇点(出度为 0),每一条边都有非负的容量,且整张图都会保证平衡状态。这样的图叫做网络流图。

基本网络流算法

最大流 – Dinic

每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次,再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。

其中值得一提的是,Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针,避免不必要的遍历。

OI

[Fortuna OJ]Jul 4th – Group A 解题报告

Posted by kal0rona on

A – 非回文数字

这道题还没写,是一道数位 DP,推荐记忆化搜索。

B – 管道

这道题是一道相当好的题目。

首先对于\(m = n – 1\)的情况,也就是树的形态下,可以考虑自下向上推,也就是从叶子节点开始推起,参考代码中 Toposort 的写法。然后,对于\(m > n\)的情况可以直接输出\(0\),因为这个方程组并不存在唯一的解:\(m\)个未知数仅提供\(n\)个条件,这样是不成立的。

最后考虑\(m = n\)的情况。这种情况就是基环树了。首先,Toposort 会把支链上的答案全部统计完毕,并且合并到环上的点。最后,我们唯一要多做的事情,就是处理环上的方程组。考虑一个这样的环: