前言
这是一道比较神仙的题目，其后半部分的建图是比较困难想到的，前半部分还是较为容易的。
题意
现在有一张\(N\)个点\(M\)条边的有向图，每个点有一个点权\(a_i\),现在要找出\(K\)条路径，使得这些路径的并集的点权和尽量大。现在求出点权和。
\(N, M \le 2\times 10^5, k \le 10\)
题解
缩成DAG
首先我们先用缩点将原图缩成一张DAG，因为一个人可以只用一次走过一个强连通分量(SCC)，这一点是显然的。
下文中，我们设\(n^{'}\)为缩完点后的DAG的大小，\(b_i\)表示第\(i\)个SCC的权值总和，用\(bel_i\)表示节点\(i\)在DAG中对应的强连通分量的编号。
并且惯用图论中的\(V\)表示DAG的点集，\(E\)表示DAG的边集。
缩小数据范围
我们先不妨缩小一下数据范围，考虑一下\(\mathcal{O}(KMN)\)的做法。这一部分的做法还是比较显然的。根据常见的套路，我们会把点权拆点边成边权，然后在根据题目具体进行连边。那么，我们不妨可以这样连边：
- \(\forall u \in V, (u, u^{'}, 1, b_u), (u, u^{'}, +\infty, 0)\) 这一部分对应拆点建边
- \(\forall (u, v) \in E, (s^{'}_u, s_v, +\infty, 0)\) 边不会产生贡献
- \((S, bel_1, K, 0)\),表示所有人都要从\(bel_1\)点出发
- \(\forall u \in V, (u^{'}, T, +\infty, 0)\),代表着任何点都可以作为重点
然后我们对这个东西跑最大费用最大流。只需在最小费用最大流上将费用取反即可。
现在我们已经做出了一种\(\mathcal{O}(KMN)\)的做法。
解决原题
现在我们想要从算法上解决问题。然后我们发现了一种叫 Primal-Dual Method的算法。个人理解是核心在于维护一个势能函数\(h\),和HLPP感觉有异曲同工之妙。
这里是详细的。
不过我们非常惊喜的发现这个东西要求费用为正。这显然非常好处理，我们记录损失了多少权值。然后连边就变成了：
- \(\forall u \in V, (u, u^{'}, 1, 0), (u, u^{'}, +\infty, b_u)\)
- \(\forall (u, v) \in E, (s^{'}_u, s_v, +\infty, \sum \limits_{i=u + 1}^{v - 1} b_i)\)
- \((S, bel_1, K, \sum \limits_{i=1}^{bel_1 - 1}b_i)\)
- \(\forall u \in V, (u^{'}, T, +\infty, \sum \limits_{i=u + 1}^{T}b_i)\)
这个就变成了最小费用最大流，跑一遍以后，答案即为\(K \times \sum \limits_{i=1}^{n}a_i-\text{mincost}\)
显然\(\sum \limits_{i=1}^{n}a_i = \sum \limits_{i \in V}b_i\)，所以其实本事是一样的
然后呢，代码就没必要放了，我全都用的是atcoder/scc和atcoder/mincostflow的东西。这边强烈建议使用，这样就不用再写一遍tarjan/kosaraju和MCMF了(手动狗头)