[bzoj1449/2895]-[JSOI2009]球队收益

人生第一次在linux下写(用的deepin)……

千年八云紫:你noip干嘛去了?

题目(BZOJ)

题目(洛谷)

 

这题主要是建模比较巧,如果你做过bzoj2597那么这题应该很好做。

(顺便吐槽一下bzoj2597,居然卡常!)

首先,假设每场比赛每个人都输,计算出初始答案,

之后考虑每一场比赛:不难发现一场比赛只能有一个人赢,我们可以抽象地认为这场比赛 $$i$$ 赢的话就是该比赛向 $$i$$ 提供了 $$1$$ 的流量。

同时还发现,一个队的输赢是不影响其他队伍的,并且我们一开始假设每场比赛每个队都输,也就是说我们要决定哪些队伍赢。从输到赢会增加一定费用,所以对于第 $$i$$ 支队伍,向汇点 $$T$$ 连 $$x$$ 条弧($$x$$ 代表该队伍最多赢的场数),容量为 $$1$$,费用为 $$2*C_i*win_i+C_i+D_i-2*D_i*lose_i$$,并且每次加弧长时,$$win_i++$$,$$lose_i–$$。

最后跑一次费用流,完毕。

 

[bzoj1449/2895]-[JSOI2009]球队收益》上有1条评论

发表评论