「网络流24题」最长k可重区间集 优化建图

Posted on | In , ,

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

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

题目链接

建图分析

最长k可重区间集，若将线段看成点，可以看做选择k条不相交路径(因为每个点只能选一次)的权值和最大。

方法1：直接按照朴素的想法建图。

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

  • 连接S到S’一条容量为K，费用为0的有向边。
  • 从S’到每个<i.a>连接一条容量为1，费用为0的有向边。
  • 从每个<i.b>到T连接一条容量为1，费用为0的有向边。
  • 从每个顶点<i.a>到<i.b>连接一条容量为1，费用为区间长度的有向边。
  • 对于每个区间i，与它右边的不相交的所有区间j各连一条容量为1，费用为0的有向边。
    边数是O(N^2)，求最大费用最大流，最大费用流值就是最长k可重区间集的长度。

方法2：改变一下思路，把端点作为网络中的顶点，区间恰恰是特定一些端点之间的边，这样建模的复杂度更小。

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

  • 从S到顶点1（最左边顶点）连接一条容量为K，费用为0的有向边。
  • 从顶点2N（最右边顶点）到T连接一条容量为K，费用为0的有向边。
  • 从顶点i到顶点i+1 $(i+1\le n)$，连接一条容量为无穷大，费用为0的有向边。
  • 对于每个区间[a,b]，从a对应的顶点i到b对应的顶点j连接一条容量为1，费用为区间长度的有向边。
    边数是O(N)。求最大费用最大流，最大费用流值就是最长k可重区间集的长度。

代码

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2005;
const int INF=1e9+7;


struct Edge
{
    int from, to, cap, flow, cost;
    Edge(int u,int v,int c,int f, int w):from(u), to(v), cap(c), flow(f), cost(w) {}
};

struct MCMF
{
    int n, m;
    vector<Edge> edges;   // 边数的两倍
    vector<int> G[maxn];  // 邻接表，G[i][j]表示节点i的第j条边在e数组的序号
    int inq[maxn];        // 是否在队列中
    int d[maxn];          // Bellman-Ford
    int a[maxn];          // 当起点到i的可改流量
    int p[maxn];          // 最短路树上p的入弧编号(path路径)

    void init(int n)
    {
        this->n = n;
        for(int i=0; i<=n+1; i++)
            G[i].clear();
        edges.clear();
    }

    void Addedge(int from, int to, int cap,int cost)
    {
        edges.push_back(Edge(from, to, cap, 0, cost));
        edges.push_back(Edge(to, from, 0, 0, -cost));
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BellmanFord(int s,int t,int& flow, long long& cost)
    {
        for(int i=0; i<=n; i++)
            d[i] = 1000000000+2;
        memset(inq, 0, sizeof(inq));
        d[s]=0; inq[s]=1; p[s]=0; a[s]=1000000000+2;

        queue<int> Q;
        Q.push(s);

        while(!Q.empty())
        {
          //  cout<<123<<endl;
            int u=Q.front();
            Q.pop();
            inq[u]=0;
            for(int i=0; i<G[u].size(); i++)
            {
                Edge& e=edges[G[u][i]];
                if( e.cap > e.flow && d[e.to] > d[u]+e.cost)
                {
                    d[e.to]=d[u]+e.cost;
                    p[e.to] = G[u][i];
                    a[e.to] = min(a[u], e.cap-e.flow);
                    if(!inq[e.to]){ Q.push(e.to); inq[e.to]=1;}
                }
            }
        }
        if(d[t] == 1000000000+2)
            return false;
        flow += a[t];
        cost += (long long)d[t] * (long long)a[t];
        for(int u=t; u!=s; u=edges[p[u]].from)
        {
            edges[p[u]].flow += a[t];
            edges[p[u]^1].flow -= a[t];
        }
        return true;
    }

    void MincostMaxflow(int s,int t,long long& cost)
    {
        int flow=0; cost=0;
        while(BellmanFord(s, t, flow, cost));
        //return flow;
    }
};

int n, k, l[maxn],r[maxn], b[maxn], ll[maxn], rr[maxn];

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d", &l[i], &r[i]);
        if(r[i]<l[i])
            swap(l[i],r[i]);
        b[i]=l[i];
        b[i+n]=r[i];
    }
    sort(b+1, b+2*n+1);
    int w=unique(b+1, b+2*n+1)-b;
    int st=0, ed=maxn-2;
    MCMF now;
    now.init(ed);
    now.Addedge(st, 1, k, 0);
    now.Addedge(w-1,ed,k,0);
    for(int i=1;i<=n;i++)
    {
        int p=lower_bound(b+1, b+w, l[i])-b;
        ll[i]=p;
        p=lower_bound(b+1, b+w, r[i])-b;
        rr[i]=p;
        now.Addedge(ll[i], rr[i], 1, -(r[i]-l[i]));
    }
    for(int i=1;i<w-1;i++)
        now.Addedge(i,i+1, INF, 0);
    long long ans;
    now.MincostMaxflow(st,ed,ans);
    printf("%lld\n", -ans);


}