餐巾计划问题

题目链接
将每个点拆成白天和晚上,白天只收干净的餐巾,晚上只收脏餐巾,从源点往每天晚上连容量为x,费用为0的边,表示每天晚上会收到x条脏餐巾。
从每天早上往汇点连容量为x,费用为0的边,流满表示餐巾够用。
从每天晚上往下一天晚上连容量inf,费用0的边,表示留到下一天。
从每天晚上往快洗结束[……]

继续阅读

方格取数问题

题目链接
给n*m的方格图,然后取数,要求取出来的数的位置不相邻,问最大值。
因为每个点只对他四周的点有影响,那么将点进行奇偶分隔,然后源点向奇点连边,偶点往汇点连边,然后奇点往周围的偶点连边,跑出最大流即最小割,即要扣去的代价,用总和减去即可。


#include <bits/std[......]

继续阅读

试题库问题

题目链接
咕咕咕咕咕咕二个半月。。。。
给k个题目类型和n个题目,然后要求组成一套有\(a_i\)个i类试题的试卷,每个题目可以对应p类题目,但是只能作为一类使用,求组出的题目。
源点往题目连边1,题目往类型连边1,类型往汇点连需要个数,最大流。


#include <bits/st[......]

继续阅读