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

时间：2023-12-21 16:46:38

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

内存限制：256 MiB时间限制：1000 ms标准输入输出
题目类型：传统评测方式：文本比较
上传者： 匿名

题目描述

给定实直线 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 2

1 7

6 8

7 10

9 13

样例输出

15

数据范围与提示

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

题目链接：https://loj.ac/problem/6014

题意：中文题意，意思明显。

思路：当k=1时，这个问题等价于从n个区间选取一个元素互不相交的子集，目标是最大化子集权重和。这个问题又被称为区间图的最大权独立集。这个问题可以用dp算法求解,也可以看做是一个最短路问题（注意建图方式）。所以最长 k 可重区间集，即求k条最短路，费用流。

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<set>

#include<queue>

#include<stack>

#include<map>

#include<vector>

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

#define PI acos(-1.0)

const int maxn=1e5+,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+;

const ll INF=1e18+;

struct edge

{

    int from,to;

    int cap,flow;

    int w;

};

vector<edge>es;

vector<int>G[maxn];

int pre[maxn];

int dist[maxn];

inline void init(int n)

{

    es.clear();

    for(int i=; i<=n+; i++) G[i].clear();

}

inline void addedge(int from,int to,int cap,int w)

{

    es.push_back((edge)

    {

        from,to,cap,,w

    });

    es.push_back((edge)

    {

        to,from,,,-w

    });

    int num=es.size();

    G[from].push_back(num-);

    G[to].push_back(num-);

}

bool SPFA(int s,int t)

{

    static queue<int>q;

    static bool inq[maxn];

    for(int i=; i<maxn; i++) inq[i]=false,dist[i]=inf;

    dist[s]=;

    q.push(s);

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        inq[u]=false;

        for(int i=; i<G[u].size(); i++)

        {

            edge e=es[G[u][i]];

            if(e.cap>e.flow&&dist[e.to]>dist[u]+e.w)

            {

                pre[e.to]=G[u][i];

                dist[e.to]=dist[u]+e.w;

                if(!inq[e.to]) q.push(e.to),inq[e.to]=true;

            }

        }

    }

    return dist[t]<inf;

}

void dinic(int s,int t,int f)

{

    int flow=,cost=;

    while(SPFA(s,t))

    {

        int d=f;

        for(int i=t; i!=s; i=es[pre[i]].from)

            d=min(d,es[pre[i]].cap-es[pre[i]].flow);

        f-=d;

        flow+=d;

        cost+=d*dist[t];

        if(f<=) break;

        for(int i=t; i!=s; i=es[pre[i]].from)

            es[pre[i]].flow+=d,es[pre[i]^].flow-=d;

    }

    printf("%d\n",-cost);

}

int l[maxn],r[maxn],w[maxn];

int c[maxn<<];

int compress(int n)

{

    memcpy(c+,l+,sizeof(l));

    memcpy(c+n+,r+,sizeof(r));

    sort(c+,c+*n+);

    int SIZE=unique(c+,c+*n+)-(c+);

    for(int i=; i<=n; i++)

    {

        l[i]=lower_bound(c+,c+SIZE,l[i])-c;

        r[i]=lower_bound(c+,c+SIZE,r[i])-c;

    }

    return SIZE;

}

int main()

{

    int n,k;

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

    for(int i=; i<=n; i++)

    {

        scanf("%d%d",&l[i],&r[i]);

        if(r[i]<l[i]) swap(l[i],r[i]);

        w[i]=r[i]-l[i];

    }

    int s=,t=compress(n);

    for(int i=; i<t; i++)

        addedge(i,i+,inf,);

    for(int i=; i<=n; i++)

    {

        ///cout<<l[i]<<" * "<<r[i]<<" * "<<w[i]<<endl;

        addedge(l[i],r[i],1,-w[i]);

    }

    dinic(s,t,k);

    return ;

}

最小费用流

相关文章