2026.2.24
Codechef RIN
\(\color{blue}{网络流}\)
最大平均分等价与最大化得分和等价于最小化扣分和。考虑最小割模型。对于每个课程，建立 \(m\) 个点 \(a_1,a_2,\cdots,a_m\)，然后 \(s\to a_1, a_1\to a_2, \cdots, a_m\to t\)。其中 \(a_m \to t\) 的边权为正无穷，其他边的边权为学完这门课的扣分。在最小割中选择 \(a_{i-1}\to a_i\) 就是扣这门课的分。考虑特殊限制，对于每个限制，可以从 \(a_i \to b_{i+1}\) 连边权为正无穷的边。这样如果 \(a\) 在 \(b\) 之后学习，依旧可以通过这条边从 \(s\) 跑到 \(t\)，所以是对的。跑最小割即可。
Luogu P3973 [TJOI2015] 线性代数
\(\color{blue}{推式子，网络流}\)
假设先把所有 \(b_{i,j}\) 全部去掉，可以发现对于每个 \(b_{i,j}\)，如果在 \(A\) 矩阵中填 \(0\) 就会损失 \(b_{i,j}\)，否则就会损失 \(c_i+c_j\)。容易想到最小割。考虑源点向 \(B\) 中每个元素连一条流量为 \(b_{i,j}\) 的边，\(C\) 中每个元素向汇点连流量为 \(c_i\) 的边，每个 \(b_{i,j}\) 向 \(c_i,c_j\) 连流量为正无穷的边。这样对于每个 \(b_{i,j}\)，如果想切断源点和汇点的路径，必须在 \(b_{i,j}\) 和 \(c_i+c_j\) 中选择一个。跑最小割即可
Luogu P2053 [SCOI2007] 修车
\(\color{blue}{网络流}\)
考虑最小化总时间。如果只有一个工人，那么总时间为 \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}T_i\times (n-i+1)\)，所以每辆车的贡献为 \(T_i\times (n-i+1)\)。考虑把每个工人拆成 \(n\) 个点，表示他洗了多少个车。第 \(i\) 个车向低 \(j\) 个工人第 \(k\) 的阶段连一条流量为 \(1\)，费用为 \(T_i\) 的边。源点和汇点分别向车和人连流量为 \(1\)，费用为 \(0\) 的边。跑最小费用最大流即可。