题解 P4307 【[JSOI2009]球队收益 / 球队预算】

2019-01-20 22:09:16


这题好神仙啊qwq


考虑费用流。

先从源点向每场比赛连容量为 $1$ ,费用为 $0$ 的边,从每场比赛都参加这场比赛的两方连容量为 $1$ ,费用为 $0$ 的边。

先假设所有队在所有比赛中全负。再设第 $i$ 支球队胜 $a[i]$ 场,负 $b[i]$ 场。

每个球队多赢一场,预算会增加 $c\times(2\times a[i]+1)-d\times(2\times b[i]-1)$ 。

然后每支球队向汇点连 $b[i]$ 条容量为 $1$ ,费用为上面这个东西的边,每连一条边就将 $a[i]$ 加 $1$ , $b[i]$ 减 $1$ 。

然后跑一遍费用流,最小费用加上全负的花费就是答案。


代码见blog