#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_ili 和 ri r_iri，表示开区间的左右端点坐标，注意可能有 li>ri l_i > r_ili>ri，此时请将其交换。

输出格式

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

样例

样例输入

样例输出

数据范围与提示

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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#define maxn 1010

#define INF 1000000000

using namespace std;

int n,k,mp[maxn],m,l[maxn],r[maxn],S,T,head[maxn],num=,dis[maxn],ans;

bool vis[maxn];

struct node{int to,pre,v,w;}e[];

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=;e[num].w=-w;e[num].pre=head[to];head[to]=num;

}

int find(int x){return lower_bound(mp+,mp+m+,x)-mp;}

void build(){

    S=;T=m+;

    Insert(S,,k,);Insert(m,T,k,);

    for(int i=;i<m;i++)Insert(i,i+,INF,);

    for(int i=;i<=n;i++)Insert(find(l[i]),find(r[i]),,-r[i]+l[i]);

}

bool spfa(){

    queue<int>q;

    memset(vis,,sizeof(vis));

    memset(dis,0x3f,sizeof(dis));

    q.push(S);vis[S]=;dis[S]=;

    while(!q.empty()){

        int now=q.front();q.pop();vis[now]=;

        for(int i=head[now];i;i=e[i].pre){

            int to=e[i].to;

            if(e[i].v>&&dis[to]>dis[now]+e[i].w){

                dis[to]=dis[now]+e[i].w;

                if(!vis[to]){vis[to]=;q.push(to);}

            }

        }

    }

    return dis[T]<INF;

}

int dinic(int x,int flow){

    if(x==T||flow==)return flow;

    int rest=flow;vis[x]=;

    for(int i=head[x];i;i=e[i].pre){

        int to=e[i].to;

        if(dis[to]==dis[x]+e[i].w&&e[i].v>&&!vis[to]){

            int delta=dinic(to,min(rest,e[i].v));

            e[i].v-=delta;

            e[i^].v+=delta;

            rest-=delta;

            ans+=e[i].w*delta;

        }

    }

    vis[x]=;

    return flow-rest;

}

void work(){

    while(spfa()){

        memset(vis,,sizeof(vis));

        dinic(S,INF);

    }

}

int main(){

    scanf("%d%d",&n,&k);

    for(int i=;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+,mp+m+);

    m=unique(mp+,mp+m+)-mp-;

    build();

    work();

    ans=-ans;

    printf("%d",ans);

}

秒客网

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