zkw费用流:多路增广,增光D[y]=D[i]+c的边
每次强行增加下界的流量
类似网络流,拆边
原边的费用为c,拆出来的边费用为0
我的思路:
建出i*bi个点,如果ai是aj的质数倍,从bi个点向bj个点连边
跑有上下界可行费用最大流(woc这是个什么东西。。)
正解
两个数能够配对,分解后指数之和差为1则可以匹配
按照差值分为两类
不断增广
有上下界最大费用最大流
——》限制相等的情况,可以通过加一维费用来解决
时间复杂度:N^5
对于回路上的点,其出度入度都为1
根据题意,每个点的出度都为1
我的思路:
找出入度不为1的点,2^n枚举是否更改(好傻逼)
正解
黑白染色,建二分图
从一个点向四个方向连边,(1,0) (1,1)(1,1) (1,1)
黑白染色后对度数进行限制
考虑如何处理费用
拆点,把一个点拆成两个,连流量为1的边,如果是直的,那么一定会经过中间的边,问题便可以得到解决
平方的性质满足费用递增
二分图模型
按照天数建点
每一天有三种方案
对于每个区间,分别列出等式
对每个等式进行差分
可以看到差分后数组左边的每个变量都出现了两次
GG
二叉树