网络流区间覆盖模型

区间覆盖

$[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$ 都相等，就没有下界变成普通费用流了。

但是，一般情况都是 $a_i=0$，$b_i$ 不固定。但是在上界没有限制的情况下，可以通过直接从源点补充流量和直接向汇点消耗流量来避免流量下界界。即若 $b_i<b_{i+1}$，则 $i\to i+1$ 的下界比 $i+1\to i+2$ 的大 $b_{i+1}-b_i$，就从 $S$ 向 $i+1$ 补充 $b_{i+1}-b_i$ 的流量。反之，就从 $i+1$ 向 $T$ 消耗掉 $b_i-b_{i+1}$ 的流量即可。在边界有 $b_0=b_{n+1}=0$。

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]$ 次。

P3337

对偶之后流。