Official
H - Collecting Editorial by en_translator
The items in the same strongly-connected component can be picked up when visiting it for the first time. Therefore, we can merge each strongly-connected component into one to assume the graph as a DAG (Directed Acyclic Graph).
Hereinafter we assume that the graph is a DAG, and Vertices \(1, 2, \dots,\) and \(N\) are sorted topologically. The problem can be boiled down to a minimum-cost flow problem.
You may first come up with the following way:
- For \(1 \leq u \leq N\), prepare vertices \(\mathrm{in}_u, \mathrm{out}_u\). Also, prepare \(S\) and \(T\) as the source and the sink.
- For \(1 \leq u \leq N\), add an edge from \(\mathrm{in}_u\) to \(\mathrm{out}_u\) with capacity \(1\) and cost \(-X_u\), and another edge with capacity \(\infty\) and cost \(0\).
- For every edge \((u, v)\), add an edge from \(\mathrm{out}_u\) to \(\mathrm{in}_v\) with capacity \(\infty\) and cost \(0\).
- Add an edge from \(S\) to \(\mathrm{in}_1\) with capacity \(\infty\) and cost \(0\).
- For \(1 \leq u \leq N\), add an edge from \(\mathrm{out}_u\) to \(T\) with capacity \(\infty\) and cost \(0\).
- The answer is the minimum cost from \(S\) to \(T\) of flow \(K\), multiplied by \(-1\).
However, this method gives rise to edges with negative costs. We can remove the negative edges as follows:
- For \(1 \leq u \leq N\), add an edge from \(\mathrm{in}_u\) to \(\mathrm{out}_u\) with capacity \(1\) and cost \(0\), and another edge of capacity \(\infty\) and cost \(X_u\).
- For every edge \((u, v)\), add an edge from \(\mathrm{out}_u\) to \(\mathrm{in}_v\) with capacity \(\infty\) and cost \(X_{u + 1} + \dots + X_{v - 1}\).
- Add an edge from \(S\) to \(\mathrm{in}_1\) with capacity \(\infty\) and cost \(0\).
- For \(1 \leq u \leq N\), add an edge from \(\mathrm{out}_u\) to \(T\) with capacity \(\infty\) and cost \(X_{u + 1} + \dots + X_N\).
- The answer is the minimum cost from \(S\) TO \(T\) of flow \(K\), subtracted from \(K \left(\sum_u X_u \right)\).
posted:
last update: