笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

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

posted on 2020-03-18 08:31:10 | under 题解 |

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

本人十分不赞同,对于一道网络流题,一篇题解只说怎么建图不说思路的行为。我就想请问,难道做一道题的目的,就只在于做这一道题吗?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 ;
}