2024.6 做题记录

[JSOI2009] 球队收益 / 球队预算

考虑到要求最小总支出，想到最小费用流。

首先容易发现，每场比赛都只有两种可能，即甲输乙赢或甲赢乙输。但是这样我们在跑费用流的时候显然需要考虑对于两个因素同时的影响，显然这样不好做。我们不妨假设剩下的比赛所有人都输，那么我们就只需要考虑每一场比赛赢的贡献即可。

现在我们先考虑建图。首先有 \((s,ss,m,0)\) 表示 \(m\) 场比赛的限制，然后应该有 \((s_i,i+n,1,0),(t_i,i+n,1,0),(i+n,t,1,0)\)，也就是从比赛双方球队向比赛连边，流量是 \(1\)。然后再从比赛向汇点连边，流量为 \(1\)，这样就可以限制每场比赛的胜利者只有一个。

现在的问题就在于如何计算赢一场比赛的贡献，也就是 \(ss\) 和球队 \(i\) 之间怎样连边。

考虑我们原先假设的是所有球队都输，于是如果一支球队在 \(m\) 场比赛中打了 \(p_i\) 场，原先的费用就应该是 \(c_i{a_i}^2+d_i(b_i+p_i)^2\)。现在考虑如果这支球队赢了 \(q_i\) 场，那么现在的费用就是 \(c_i(a_i+q_i)+d_i(b_i+p_i-q_i)^2\)。现在对两者做差，就可以求出赢 \(q_i\) 场对答案的贡献为：

如果将 \(q_i\) 看作流量，那么发现式子中出现了平方费用流，考虑拆边处理。设上式中 \(q_i\) 系数为 \(A\)，\({q_i}^2\) 系数为 \(B\)，则我们从 \(ss\) 向 \(i\) 连边 \((1,A+B),(1,A+3B),(1,A+5B),\cdots,(1,A+(2p_i-1)B)\)。其实相当于将原来 \(q_i\) 的流量拆成 \(1\) 的流量，然后累加起来达到平方费用的效果。

最后我们跑最小费用最大流，最小费用再加上假设所有队都输的费用就是最后答案。