问题:有n个东西,分给m个人,对于每个东西,每个人有喜欢与不喜欢两种态度:like[i][j],如果喜欢,那么他得到该东西时增加的喜悦度为k,否则为1,问是否存在一种分法,使得每个人都达到该人的最低喜悦度b[i]。

建模方法:

src->thing[i] cost = 0, cap = 1

kid[i]->dst : if b[i]/k != 0 : cost = k, cap = b[i]/k

        if b[i]%k!=0 : cost = b[i]%k, cap = 1

thing[i]->kid[j] : if like[j][i] : cost = 0, cap = 1

求出最大费用最大流:cost, flow

如果:cost+(n-flow) >= sum of b,则存在一种分法。
否则不存在。

————————————

收获:

  1、“该区分的区分,该不区分的不区分”,本题而言,对于所有喜欢的东西,如果它选了p个,那么选的p个对kid而言不区分,所以用流量表示个数,费用表示一个的贡献。

    对于kid不喜欢的东西,也是一类不区分的,只需要知道还差几个不区分的就行了。

  2、“最大化必须的”。。。。。。

05-11 15:11