餐巾计划问题

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

继续阅读

方格取数问题

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


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

继续阅读

试题库问题

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


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

继续阅读

最长不下降子序列

给你n个数,第一问要求求出最长不下降子序列长度s,第二问在每个数字只使用一次的情况下,求出长度为s的不下降子序列有多少个,第三问\(a_1\)和\(a_n\)可以使用无限次的情况下长度为s的不下降子序列有多少个。
解 第一问用n^2的lis求解,并存dp[i]为从1到i的最长不下降子序列长度,然后[……]

继续阅读

圆桌问题

有m个单位,每个单位有\(r_i\)个人,要分配到n张桌子,每个桌子可以容纳\(c_i\)的人,要求相同单位的人不能同一张桌子上,问能否分配及分配方法。
解 很显然的一道网络流,源点往单位建单位人数的边,桌子往汇点建容纳人数的边,每个单位向每个桌子建流量为1的边,这样可以保证每个单位最多只有1个人[……]

继续阅读

魔术球问题

给n个柱子,要依次放入1,2,3,……的球,要求每根柱子相邻的球的和为完全平方数,问最多能放几个球。
可以理解为 你最多可以有多少个球把他们分成n组。同样使用最小边覆盖=点数-最大匹配
先拆成二分图,在和为平方数的点之间加边,源点往x连,汇点往y连。不断加入新点,跑新的最大流(新的是多出来的,所[……]

继续阅读

最小路径覆盖问题

给一个有向无环图,要求你用最少的路径(所有路径不重复经过一个点)包含图中所有点,最少需要几条路径。
最小边覆盖=总数-最大匹配。先一开始当n条,然后考虑路径合并,每有两条路径合在一起,那么覆盖数就-1。所以,将点拆成x和y,源点向x连1,y向汇点连1,然后把给的边从x连到y,这样跑出的最大流即是路[……]

继续阅读

太空飞行计划

有n个实验,每个实验有一定的收益,同时每个实验需要一定的仪器,仪器需要一定的代价,问最多收益。
解 先假设所有实验收益都得到,然后就有2种损失,要么损失掉这个实验的收益(即不需要买仪器),或者损失掉仪器的价格(获得该实验的收益)。源点往实验连实验的收益,仪器往汇点连仪器的价格,实验往仪器连inf([……]

继续阅读