网络流模型

区间覆盖

$[1,n]$ 中 $m$ 个区间 $[l_i,r_i]$，代价 $w_i$，个数 $c_i$。要求使每个点被覆盖 $[a_j,b_j]$ 次。

用边 $i\to i+1$ 的流量描述 $i$ 被覆盖的次数。设总流量 $lim=\max b_j$。连边 $(l_i,r_i+1,c_i,w_i)$ 和 $(j,j+1)$ 流量为 $[lim-b_j,lim-a_j]$ 费用为 $0$。每当 $i$ 被覆盖一次，$i\to i+1$ 流量就少 $1$。

上下界网络流，如果 $b$ 都相等，就没有下界变成普通费用流了。

Q7762

给点 $w_1,\cdots w_n$。有一个长为 $m$ 的初始全零的序列 $a$。$q$ 次请求 $k_i$，如果不存在 $a_{pos}=k_i$，加 $w_{k_i}$ 代价使一个位置 $a_{pos}=k_i$。

转换为最多减去多少代价。等价于：对于上一个 $k_p=k_i$ 的请求 $p$，如果 $p$ 到 $i$ 都一直不动 $p$ 处取到 $k_p$ 的位置，就能减少 $w_{k_i}$ 的代价。即线段 $[p+1,i-1]$，最后每个点被覆盖 $\le m-1$。

Q3304

选择价值最大的一些区间，对区间按包含关系连边，要求不成环。

等价于：没有三个互相相交的区间。即每个点被覆盖 $\le 2$ 次。

P6967

$n$ 个小时，睡觉和吃饭价值分别为 $s_i$ 和 $e_i$。要求每 $k$ 个小时睡 $m_e$ 和吃 $m_s$ 小时。

先当做全睡觉，再选一些位置变为吃饭。等价于：把 $i$ 小时吃饭看成区间 $[i,i+k)$，对于 $i\ge k$ 的位置被覆盖 $[m_e,k-m_s]$ 次。