「Luogu3358」 最长k可重区间集问题

problem

Solution

最大费用最大流模型。

约定：下文采用格式(u,v,f,c)(u,v,f,c)表示以uu为起点，vv为终点，ff为流量，cc为费用的边；SS为源，TT为汇

最终实现需要对坐标离散化

称与这些区间有关的线段(1,n)(1,n)为“总线段”，连边(S,1,K,0)(S,1,K,0)，(n,T,K,0)(n,T,K,0)（限流）。

对于总线段上的每个点，连边(i,i+1,inf,0)(i,i+1,inf,0)

对于每个区间，连边(l[i],r[i],1,r[i]−l[i])(l[i],r[i],1,r[i]-l[i])

跑最大费用最大流即可

Code

实际实现中采用了取相反数跑最小费用的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
#define maxn 1505
using namespace std;
typedef long long ll;

template <typename T>void read(T &t)
{
    t=0;char c=getchar();int f=0;
    while(!isdigit(c)){f|=c=='-';c=getchar();}
    while(isdigit(c)){t=t*10+c-'0';c=getchar();}
    if(f)t=-t;
}

const int inf=0x3f3f3f3f;
int n,K;
int l[maxn],r[maxn],v[maxn];
int s,t,ansc;

struct edge
{
    int u,v,f,c,nxt;
}g[maxn*8];

int head[maxn],ecnt=1;
void eADD(int u,int v,int f,int c)
{
    g[++ecnt].u=u;
    g[ecnt].v=v;
    g[ecnt].f=f;
    g[ecnt].c=c;
    g[ecnt].nxt=head[u];
    head[u]=ecnt;
}

int dist[maxn],inq[maxn],minf[maxn];
int pree[maxn],prev[maxn];
bool SPFA()
{
    memset(dist,0x3f,sizeof(dist));
    memset(minf,0x3f,sizeof(minf));
    queue<int> q;
    q.push(s);
    dist[s]=0;
    inq[s]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(register int i=head[u];i;i=g[i].nxt)
        {
            int v=g[i].v;
            if(g[i].f && dist[v]>dist[u]+g[i].c)
            {
                dist[v]=dist[u]+g[i].c;
                prev[v]=u;
                pree[v]=i;
                minf[v]=min(minf[u],g[i].f);
                if(!inq[v])q.push(v);
            }
        }
    }
    return dist[t]<inf;
}

int main()
{
    read(n),read(K);
    int ocr[maxn];
    for(register int i=1;i<=n;++i)
    {
        read(l[i]),read(r[i]),v[i]=r[i]-l[i];
        ocr[i*2-1]=l[i],ocr[i*2]=r[i];
    }
    sort(ocr+1,ocr+2*n+1);
    ocr[0]=unique(ocr+1,ocr+2*n+1)-ocr-1;
    for(register int i=1;i<=n;++i)
        l[i]=lower_bound(ocr+1,ocr+ocr[0]+1,l[i])-ocr,r[i]=lower_bound(ocr+1,ocr+ocr[0]+1,r[i])-ocr;
    s=0,t=ocr[0]+1;
    eADD(s,1,K,0),eADD(1,s,0,0);
    eADD(ocr[0],t,K,0),eADD(t,ocr[0],0,0);
    for(register int i=1;i<ocr[0];++i)
        eADD(i,i+1,inf,0),eADD(i+1,i,0,0);
    for(register int i=1;i<=n;++i)
        eADD(l[i],r[i],1,-v[i]),eADD(r[i],l[i],0,v[i]);
    while(SPFA())
    {
        ansc+=minf[t]*dist[t];
        for(register int i=t;i!=s;i=prev[i])
        {
            g[pree[i]].f-=minf[t];
            g[pree[i]^1].f+=minf[t];
        }
    }
    printf("%d",-ansc);
    return 0;
}