BZOJ 3442 学习小组

发布于 2017-06-22  148 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3442

题意:n 个学生,m 个学习小组,一个学生最多参加 k 个学习小组,每个学生参加学习小组都要交一定的手续费,若有 a 个学生参加第 i 个学习小组,那么给这个学习小组组织者奖励\(C_i*a^2\) 元,在参与学生尽量多的情况下,最少要支出多少钱。


约定

在本文中,形如 (i,j) 的二元组意为一条 flow=i,cost=j 的有向边

参与学生尽量多,支出尽量小,比较能让人想到最小费用最大流的模型... 于是尝试建图

发现奖励支出是有平方项的,这就不能用朴素的建边方法了... 于是膜题解知道了一个新姿势:拆边,对于一个\(C_i*a^2\),对于每个 i,都可以用\(C_i*1、C_i*3、C_i*5、C_i*7\)、... 的一堆边的前缀和表示,那么在建边的时候这么搞就好了,由于有最小费用的限制,每次增广会按照顺序跑。

别的地方就没有什么特殊的了, 每个学习小组向 T 连上述边,S 向每个学生连一条 (k,0),每个学生向其能参加的学习小组连一条 (1,\(F_i\))

题目的限制是学生必须有流通过不必满流,所以每个学生向 T 连一条 (k-1,0) 即可

 


一个非常弱的准退役OIER