题解 P3358 【最长k可重区间集问题】

感觉此题大部分题解都一点也不负责任。

本人十分不赞同，对于一道网络流题，一篇题解只说怎么建图不说思路的行为。我就想请问，难道做一道题的目的，就只在于做这一道题吗？A了就好？原理思路什么爱管不管？这能叫题解？

网络流题的重点就是在于建图。如果这都能一笔带过，那还做个锤子？

毫不夸张的说，如果张三做网络流题的时候就这么似是而非，就算他勤勤恳恳地做完了24题，省选的时候也运气好遇到了网络流题，做出来的概率绝对不高，或者说就根本不可能做出来。

你说，网络流题是什么？到现在为止还只是一个靠经验和阅历通杀的题目类别。所以网络流题需要格外重视经验的积累，知其然知其所以然。

总之呢，一道网络流题，不仔细分析思路直接告诉你怎么建图，就是在耍流氓。

给定实直线 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 可重区间集的长度。

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

首先一拿出来，这不就是匹配问题嘛？一个点最多匹配 k 个区间。于是每个位置建一个点，然后连向覆盖自己的点，然后…好像不太对？其一他没给下标的取值范围，其二一个线段覆盖多个点，要么都覆盖要么都不覆盖，这个限制很难表示…

于是好像不知道从何处入手了。发现一个这样的性质，就是永远不会选择 k 个以上交于 1 点的区间。也就是说，如果两个区间彼此之间没有交，就可以同时选；否则能不能同时选，看情况。这像极了「限制」，也就是如果两个区间之间没有交，那两者不存在限制；否则存在 k 的限制。

根据一开始的匹配，可以猜到大致上用网络流是可行的。并且似乎网络流很适合用流量来表征限制。那么考虑，如果两个区间不存在限制，那么应该怎么办——网络流类似电流，所以此时如果串联的话，就代表着可以同时选；那么如果存在限制，就意味着不能串联。根据这一点，考虑如何串联。发现本质上是将两个不交的区间中间连 f=\infty,c=0 的边。

这一点就引申出两个建图方法，其本质是相同的：

1、建立一个超级源 \rm S 和一个源 \rm S' ，中间连 f=k,c=0 的边，目的是提供初始流量。\rm S' 向每个区间的左端点连一条 f=1,c=-1 边。然后区间左端点向右端点连边 f=1,c=-len 表示贡献，每个右端点再向 \rm T 连边即可。如果两个区间不交，就由一个区间的 r 连向另一个区间的 l （当然要按秩啦）。思考这样做的合理性，对于相交的区间，一定是并联；否则的话就是串联（其实叫做混连，但是问题不大）。

2、建立一个源 \rm S 连向数轴上的 0 位置，f=k,c=0。然后数轴上每个 i>0 向 i+1 连边 f=k,c=0。最后 maxright 向 \rm T 连边。对于一个区间，连法跟1相同。

注意：

1、为什么要拆点？此处拆点的作用值得注意。对于一个区间，本质上应该抽象成一个点。但是在流图里是不存在「点权」这个概念的。所以需要把点权转边权，拆点的作用便在于此。

2、其实上面两个方法，可以通过初中物理里面什么「判断两个电路图是否等价」的知识来解决的233

3、由于本题保证了「开区间」，所以可以直接 l\to r,len=r-l 。当然如果是闭区间，只需要改成 l\to r+1 即可。

4、上面的第二个方案，发现最终可能存在很多数轴上的点 i 只与 i-1,i+1 连了 f=k,c=0 的边，所以是没用的，离散化掉就好了。

const int N = 200010 ;
const int I = 998244353 ;

#define ft first
#define sc second
#define to(k) e[k].to
#define fr(k) e[k].from
#define fw(k) e[k].flow
#define ct(k) e[k].cost
#define next(k) e[k].next
#define pint pair<int, int>

struct Edge{
    int to ;
    int from ;
    int flow ;
    int cost ;
    int next ;
}e[N * 2] ;

int _s ;
int _t ;
int ans ;
int res ;
int cnt ;
int n, m ;
int g[N] ;
int vis[N] ;
int dis[N] ;
int pre[N] ;
int head[N] ;
int _last[N] ;
queue <int> q ;

void add(int u, int v, int f, int c){
    to(++ cnt) = v ;
    next(cnt) = head[u] ;
    fw(cnt) = f ; ct(cnt) = c ;
    fr(cnt) = u ; head[u] = cnt ;
}
bool spfa(){
    fill(g, g + n + 1, I) ;
    fill(dis, dis + n + 1, I) ;
    fill(vis, vis + n + 1, 0) ;
    q.push(_s) ; vis[_s] = 1 ; dis[_s] = 0 ;
    while (!q.empty()){
        int x = q.front() ;
        q.pop() ; vis[x] = 0 ;
        for (int k = head[x] ; ~k ; k = next(k))
            if (dis[to(k)] > dis[x] + ct(k) && fw(k)){
                dis[to(k)] = dis[x] + ct(k) ;
                g[to(k)] = min(fw(k), g[x]) ;
                pre[to(k)] = x ; _last[to(k)] = k ;
                if (!vis[to(k)]){
                    q.push(to(k)) ;
                    vis[to(k)] = 1 ;
                }
            }
    }
    return (bool)(dis[_t] < I) ;
}
void ek(){
    while (spfa()){
        int x = _t ;
        res += g[_t] ;
        ans += g[_t] * dis[_t] ;
        //cout << g[_t] << " " << ans << endl ;
        while (x != _s){
            fw(_last[x]) -= g[_t] ;
            fw(_last[x] ^ 1) += g[_t] ;
            x = pre[x] ;
        }
    }
}

int len[N] ;
pint base[N] ;
int _n, _k, tot ;
map <int, int> Id, buc ;
map <int, int> :: iterator t ;

int main(){
    int u, v, f, c ;
    cin >> _n >> _k ; cnt = -1 ;
    memset(head, -1, sizeof(head)) ;
    for (int i = 1 ; i <= _n ; ++ i){
        cin >> base[i].ft >> base[i].sc ;
        len[i] = base[i].sc - base[i].ft ;
    }
    for (int i = 1 ; i <= _n ; ++ i){
        if (!Id.count(base[i].ft)) buc[base[i].ft] ++ ;
        if (!Id.count(base[i].sc)) buc[base[i].sc] ++ ;
    }
    add(0, 1, _k, 0) ; add(1, 0, 0, 0) ;
    for (t = buc.begin() ; t != buc.end() ; ++ t)
        Id[t->ft] = ++ tot ; _s = 0 ; _t = tot + 1 ;
    for (int i = 1 ; i <= tot ; ++ i)
        add(i, i + 1, I, 0), add(i + 1, i, 0, 0) ;
    for (int i = 1 ; i <= _n ; ++ i){
        //cout << Id[base[i].ft] << " " << Id[base[i].sc] << endl ;
        add(Id[base[i].ft], Id[base[i].sc], 1, -len[i]) ;
        add(Id[base[i].sc], Id[base[i].ft], 0, len[i]) ;
    }
    n = _t + 1 ; ek() ;
    cout << -ans << endl ;
}