网络流24题之二十一最长k可重区间集问题

填坑

«问题描述：

«编程任务：
对于给定的开区间集合I和正整数k，计算开区间集合I的最长k可重区间集的长度。
«数据输入：
由文件interv.in提供输入数据。文件的第1 行有2 个正整数n和k，分别表示开区间的
个数和开区间的可重迭数。接下来的n行，每行有2个整数，表示开区间的左右端点坐标。
«结果输出:
程序运行结束时，将计算出的最长k可重区间集的长度输出到文件interv.out中。
输入文件示例输出文件示例
interv.in
4 2
1 7
6 8
7 10
9 13

interv.out

模型

最大权不相交路径问题，可以用最大费用最大流解决。

实现

方法1

按左端点排序所有区间，把每个区间拆分看做两个顶点<i.a><i.b>，建立附加源S汇T，以及附加顶点S’。

1、连接S到S’一条容量为K，费用为0的有向边。
2、从S’到每个<i.a>连接一条容量为1，费用为0的有向边。
3、从每个<i.b>到T连接一条容量为1，费用为0的有向边。
4、从每个顶点<i.a>到<i.b>连接一条容量为1，费用为区间长度的有向边。
5、对于每个区间i，与它右边的不相交的所有区间j各连一条容量为1，费用为0的有向边。

求最大费用最大流，最大费用流值就是最长k可重区间集的长度。

方法2

离散化所有区间的端点，把每个端点看做一个顶点，建立附加源S汇T。

1、从S到顶点1（最左边顶点）连接一条容量为K，费用为0的有向边。
2、从顶点2N（最右边顶点）到T连接一条容量为K，费用为0的有向边。
3、从顶点i到顶点i+1(i+1<=2N)，连接一条容量为无穷大，费用为0的有向边。
4、对于每个区间[a,b]，从a对应的顶点i到b对应的顶点j连接一条容量为1，费用为区间长度的有向边。

求最大费用最大流，最大费用流值就是最长k可重区间集的长度。

分析

这个问题可以看做是求K条权之和最大的不想交路径，每条路径为一些不相交的区间序列。由于是最大费用流，两条路径之间一定有一些区间相交，可以看做事相交部分重复了2次，而K条路经就是最多重复了K次。最简单的想法就是把区间排序后，不相交的区间之间连接一条边，由于每个区间只能用一次，所以要拆点，点内限制流量。如果我们改变一下思路，把端点作为网络中的顶点，区间恰恰是特定一些端点之间的边，这样建模的复杂度更小。方法1的边数是O(N^2)的，而方法2的边数是O(N)的，可以解决更大规模的问题。

代码

#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <iostream>
#define N 1010
#define M 50000
#define INF 0x33333333
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
typedef pair<int,int> Pair;
struct node{int from,to,next,flow,cost;}e[M];
int tot=-1,st[M];
int n,m,x,y,z;
int pe[N],pv[N],dis[N],vis[N];
void add(int x,int y,int z,int zz){
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].flow=z;
    e[tot].cost=zz;
    e[tot].next=st[x];
    st[x]=tot;
}
void add_edge(int x,int y,int z,int zz){add(x,y,z,zz),add(y,x,0,-zz);}
queue<int>que;
bool spfa(int S,int T)
{
    for (int i=S;i<=T;i++)
        dis[i]=-INF;
    memset(vis,0,sizeof vis);
    que.push(S),vis[S]=1,dis[S]=0;
    while(!que.empty())
    {
        int now=que.front();que.pop();vis[now]=0;
        for (int i=st[now];~i;i=e[i].next)
            if (e[i].flow>0 && dis[e[i].to]<dis[now]+e[i].cost)
            {
                dis[e[i].to]=dis[now]+e[i].cost;
                pe[e[i].to]=i,pv[e[i].to]=now;
                if (!vis[e[i].to])
                    vis[e[i].to]=1,que.push(e[i].to);
            }
    }
    return dis[T]!=-INF;
}
Pair mfmc(int S,int T)
{
    int COST=0,FLOW=0,flow;
    while(spfa(S,T))
    {
        flow=0x3f3f3f3f;
        for (int i=T;i!=S;i=pv[i])
            flow=min(flow,e[pe[i]].flow);
        COST+=flow*dis[T];
        FLOW+=flow;
        for (int i=T;i!=S;i=pv[i])
            e[pe[i]].flow-=flow,e[pe[i]^1].flow+=flow;
    }
    return make_pair(FLOW,COST);
}
struct interval
{
    int x,y,l;
}in[N];
int temp[N],top;
int k;
//1、从S到顶点1（最左边顶点）连接一条容量为K，费用为0的有向边。
//2、从顶点2N（最右边顶点）到T连接一条容量为K，费用为0的有向边。
//3、从顶点i到顶点i+1(i+1<=2N)，连接一条容量为无穷大，费用为0的有向边。
//4、对于每个区间[a,b]，从a对应的顶点i到b对应的顶点j连接一条容量为1，费用为区间长度的有向边。
main()
{
    freopen("interv.in","r",stdin);
    freopen("interv.out","w",stdout);
    memset(e,-1,sizeof e);
    memset(st,-1,sizeof st);
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&in[i].x,&in[i].y),
        in[i].l=in[i].y-in[i].x,
        temp[++top]=in[i].y,temp[++top]=in[i].x;
    sort(temp+1,temp+top+1);
    for (int i=1;i<=n;i++)
        in[i].x=lower_bound(temp+1,temp+top+1,in[i].x)-temp,
        in[i].y=lower_bound(temp+1,temp+top+1,in[i].y)-temp;
//  for (int i=1;i<=n;i++)
//      printf("%d %d\n",in[i].x,in[i].y);
    int S=0,T=2*n+1;
    add_edge(S,1,k,0),add_edge(2*n,T,k,0);
    for (int i=1;i<2*n;i++)
        add_edge(i,i+1,INF,0);
    for (int i=1;i<=n;i++)
        add_edge(in[i].x,in[i].y,1,in[i].l);
    Pair ans=mfmc(S,T);
    printf("%d\n",ans.second);
}

网络流24题之二十一 最长k可重区间集问题

网络流24题之二十一最长k可重区间集问题