「Libre OJ」6014「网络流 24 题」最长 k 可重区间集题解

主要思路

这道题还是很妙的，我只想到了最大费用最大流之后就想不动了。

我们在这里介绍边数为\(O(n)\)级别的解法。考虑把所有的端点离散化为\(2n\)个连续的点，然后相邻端点\(i, i+1\)相互连接流量无限、费用为零的边。考虑区间左右端点，左端点连到右端点，流量为\(1\)，费用为区间长度。最后源点连左端点，汇点连到右端点。

这样就可以强制满流，且费用最大。

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

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

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

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

真的是玄妙重重。

我们先思考正常的暴力搜索：枚举每一次按下的颜色，然后检查继续更新。考虑用 IDA* 优化这个过程，首先估值函数就是剩下的颜色个数，因为至少需要更新这些颜色才有可能到达最终状态。然后注意控制 BFS 求连通块的个数的优化就行了。很好的一道题。

这道题真的是送分题（快要想出来直接暴力枚举+并查集的时候去看了题解，最后发现就是这么 sb）。

考虑枚举频段区间\([L, R]\)（将边进行排序，确定下界之后再枚举上界），这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集，然后合并两个集合的时候按照大小来修改答案就行了。

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

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

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

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

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

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

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