题解 P3358 【最长k可重区间集问题】

UPD on 8/14： 把线性规划那部分内容的锅修了。

我稍微说一下我对这道题目的理解吧。

我们考虑这个数轴（即区间要覆盖的东西），其中每个点都需要满足自己被覆盖不超过 k 次。但是这是个非常静态的东西，不大适合用网络流去模拟。我们把这个问题“动态化”。

怎么动态呢？我们可以考虑可以看成不断地加入区间然后叠加起来。首先，我们看到每个点的 k 限制类似于容量，于是我们考虑拆点，点容量转化为边容量。每一个区间加入进来，即水流从源点流到 l 来，然后再从 r 离开，即流向汇点，以上非常好理解，不过是不能做的，因为离散化后这个代价不好算，而且还不能保证每一个流进来的 l 一定从自己对应的 r 流出去。不过这个方法对后面的解法有很大的帮助和启发。我们放一下图。

上面拆点和把 k 设为容量的思路正解还可以用。

其中每种颜色的流入和流出对应一个区间。

既然叠加不行，我们反过来，考虑从 k 中剥离。什么叫剥离呢？我们形象化一下，把这道题想象成有 k 个人和 m 个任务，每个任务的时间的开区间为 l,r。那么我们肯定是这样安排的，第 l 时间来一个人，然后第 r+1 时间再还回来，然后给你 len 的收益。这样的话一切就好做很多了。其中人数我们转化成容量，然后从中拿一个人出来然后第 r+1 分钟换回来这个操作转化成从 l 到 r+1 的边。上图对应的此种解法的图如下。

（很形象了吧 qwq）

然后对于每个区间代表的边，费用为 len，其他边费用为 0，跑一遍最大费用最大流即可。注意要离散化。

我个人觉得有一些网络流问题的流量去形象化可以有更好的理解和思路，因为网络流本身就是一个这样的过程（这个单位的水流应该往哪里走）。有时候把网络流问题去代数化是个非常好的选择，但是有些时候反其道而行之去形象化说不定会有更好的思路和理解呢~。

复杂度的话，点数 O(n)，边数 O(n)，流量是 k，所以理论复杂度还是 O(n^2k)，实际复杂度是网络流的玄学复杂度。

上面提到了把网络流代数化是个很好的选择，那么我这里再放一个基于线性规划的网络流推导吧。（不想看的可以直接跳过看代码）。

设 p_i 为数轴上第 i 处被几个线段覆盖，x_i 为第 i 个区间选不选，z_{i,j} 表示第 i 个区间覆不覆盖第 j 个点。

p_1=\sum x_i\times z_{i,1} \le k p_2=\sum x_i\times z_{i,2} \le k ... p_n=\sum x_i\times z_{i,n} \le k

不等式转化为等式。

p_1=(\sum x_i\times z_{i,1})+y_1 = k p_2=(\sum x_i\times z_{i,2})+y_2 = k ... p_n=(\sum x_i\times z_{i,n})+y_n = k

其中 y 的范围是 0\le y\le k。

整个方程中对于不同的 z 每个变量出现次数不一致，我们考虑上下两项做差分。（套路）

p_1-p_0=(\sum x_i\times z_{i,1})+y_1 = k p_2-p_1=(\sum x_i\times (z_{i,2}-z_{i,1}))-y_1+y_2=0 ... p_{n+1}-p_{n}=(\sum x_i\times -z_{i,n})-y_n = -k

这样对于每个 i，x_i\times z_{i,j} 不为 0 当且仅当 i= 区间的左端点或右端点，且一正一负。

线性规划方程转换为网络流建边大致方法是，常数项和源汇连边，系数正代表流出，系数负代表流入。

于是我们得到建边

• 对于常数项 k 和 -k，S\to 1,c=k; n+1\to T, c=k。
• 对于 y，i\to i+1, c=k。
• 对于 x 和 z，s_i\to t_i+1, c=1。

考虑题目求的目标函数最小值，于是最小费用最大流即可。

\downarrow\texttt{Finally, the code that you want.} \downarrow

#include<bits/stdc++.h>
using namespace std;
const int N=2009,inf=0x3f3f3f3f;
typedef pair<int,int>pii;

struct Edge{int to,nxt,c,w;}e[N*2]; int hd[N],tot=1;
void add(int u,int v,int c,int w){e[++tot]=(Edge){v,hd[u],c,w};hd[u]=tot;}
void addh(int u,int v,int c,int w){add(u,v,c,w),add(v,u,0,-w);}

int n,k,s,t,mflow,cost,tmp;
int d[N]; bool in[N]; 
bool spfa(){ 
    queue<int>q; q.push(s); memset(d,0,sizeof(d)); d[s]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop(); in[u]=0;
        for(int i=hd[u],v;i;i=e[i].nxt)
            if(e[i].c&&d[v=e[i].to]<d[u]+e[i].w) {
                d[v]=d[u]+e[i].w;
                if(!in[v]) q.push(v),in[v]=1;
            }
    }
    return d[t]>0;
}
int dinic(int u,int flow) {
    int rest=flow; if(u==t) return flow; in[u]=1;
    for(int i=hd[u],v;i&&rest;i=e[i].nxt)
        if(!in[v=e[i].to]&&e[i].c&&d[v]==d[u]+e[i].w) {
            int used=dinic(v,min(e[i].c,rest));
            if(!used) d[v]=-1;
            rest-=used, e[i].c-=used, e[i^1].c+=used, cost+=used*e[i].w;
        }
    in[u]=0;
    return flow-rest;
}
pii flow(int ret=0,int tmp=0) {
    while(spfa()) while(tmp=dinic(s,inf)) ret+=tmp;
    return make_pair(ret,cost);
}
//上面为最大费用最大流MCMF模板 

struct Interval {int l,r,len;}a[N]; 
struct Num {int id,lr,val;}num[N]; int cnum;
bool cmp(const Num &a,const Num &b) {
    return a.val<b.val;
}

int main() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) {
        scanf("%d%d",&a[i].l,&a[i].r); a[i].len=a[i].r-a[i].l;
        num[i]=(Num){i,0,a[i].l}, num[i+n]=(Num){i,1,a[i].r};
    } 
    sort(num+1,num+2*n+1,cmp);
    for(int i=1;i<=n;i++) {
        scanf("%d%d",&a[i].l,&a[i].r);
        if(a[i].l>a[i].r) swap(a[i].l,a[i].r);
        a[i].len=a[i].r-a[i].l;
        num[i]=(Num){i,0,a[i].l}, num[i+n]=(Num){i,1,a[i].r};
    }
    //上面为读入+离散化 
    s=cnum+1, t=cnum+2;
    for(int i=1;i<cnum;i++) addh(i,i+1,k,0);
    addh(s,1,k,0), addh(cnum,t,k,0);
    for(int i=1;i<=n;i++)
        addh(a[i].l,a[i].r,1,a[i].len);
    //上面为建边 
    printf("%d",flow().second);
    return 0;
}