#6014. 「网络流 24 题」最长 k 可重区间集

题目描述

给定实直线 L LL 上 n nn 个开区间组成的集合 I II，和一个正整数 k kk，试设计一个算法，从开区间集合 I II 中选取出开区间集合 S⊆I S \subseteq IS⊆I，使得在实直线 L LL 的任何一点 x xx，S SS 中包含点 x xx 的开区间个数不超过 k kk。且 ∑z∈S∣z∣ \sum\limits_{z \in S} | z |​z∈S​∑​​∣z∣ 达到最大。这样的集合 S SS 称为开区间集合 I II 的最长 k kk 可重区间集。∑z∈S∣z∣ \sum\limits_{z \in S} | z |​z∈S​∑​​∣z∣ 称为最长 k kk 可重区间集的长度。

对于给定的开区间集合 I II 和正整数 k kk，计算开区间集合 I II 的最长 k kk 可重区间集的长度。

输入格式

文件的第 1 11 行有 2 22 个正整数 n nn 和 k kk，分别表示开区间的个数和开区间的可重迭数。

接下来的 n nn 行，每行有 2 22 个整数 li l_il​i​​ 和 ri r_ir​i​​，表示开区间的左右端点坐标，注意可能有 li>ri l_i > r_il​i​​>r​i​​，此时请将其交换。

输出格式

输出最长 k kk 可重区间集的长度。

样例

样例输入

4 21 76 87 109 13

样例输出

15

数据范围与提示

1≤n≤500,1≤k≤3 1 \leq n \leq 500, 1 \leq k \leq 31≤n≤500,1≤k≤3

#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define maxn 1010#define INF 1000000000using namespace std;int n,k,mp[maxn],m,l[maxn],r[maxn],S,T,head[maxn],num=1,dis[maxn],ans;bool vis[maxn];struct node{
        int to,pre,v,w;}e[200020];void Insert(int from,int to,int v,int w){    e[++num].to=to;e[num].v=v;e[num].w=w;e[num].pre=head[from];head[from]=num;    e[++num].to=from;e[num].v=0;e[num].w=-w;e[num].pre=head[to];head[to]=num;}int find(int x){
        return lower_bound(mp+1,mp+m+1,x)-mp;}void build(){    S=0;T=m+1;    Insert(S,1,k,0);Insert(m,T,k,0);    for(int i=1;i
               

q; memset(vis,0,sizeof(vis)); memset(dis,0x3f,sizeof(dis)); q.push(S);vis[S]=1;dis[S]=0; while(!q.empty()){ int now=q.front();q.pop();vis[now]=0; for(int i=head[now];i;i=e[i].pre){ int to=e[i].to; if(e[i].v>0&&dis[to]>dis[now]+e[i].w){ dis[to]=dis[now]+e[i].w; if(!vis[to]){vis[to]=1;q.push(to);} } } } return dis[T]

0&&!vis[to]){ int delta=dinic(to,min(rest,e[i].v)); e[i].v-=delta; e[i^1].v+=delta; rest-=delta; ans+=e[i].w*delta; } } vis[x]=0; return flow-rest;}void work(){ while(spfa()){ memset(vis,0,sizeof(vis)); dinic(S,INF); }}int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d%d",&l[i],&r[i]); if(l[i]>r[i])swap(l[i],r[i]); mp[++m]=l[i];mp[++m]=r[i]; } sort(mp+1,mp+m+1); m=unique(mp+1,mp+m+1)-mp-1; build(); work(); ans=-ans; printf("%d",ans);}