题解 P3357 【最长k可重线段集问题】

· · 题解

感觉这题压根没有正常的题解啊……

喷的原因可以去看我的上一篇题解:P3358Sol 戳我

由于这题需要用到 P3358 的前置芝士，所以大家如有需要可以去做完 P3358 这题再来。

给定平面 \text{x-o-y}上 n 个开线段组成的集合 \text{I}，和一个正整数 \rm k 从开线段集合 \text{I} 中选取出开线段集合 \text{S}\in \text{I}, 使得在 x 轴上的任何一点 \text{p} ， \text{S} 中与直线 \text{x}=\text{p} 相交的开线段个数不超过 \text{k} ，且 \sum_{\text{z} \in \text{S}}|z| 达到最大。这样的集合 \text{S} 称为开线段集合 \text{I} 的最长 \text{k} 可重线段集的长度。

对于任何开线段 \text{z}，设其端点坐标为 ( x_0 , y_0 ) 和 ( x_1 , y_1 )，则开线段 \text{z} 的长度 |\text{z}| 定义为： |z| = \lfloor \sqrt{ ( x_1 - x_0 ) ^ 2 + ( y_1 - y_0 )^2 } \rfloor。对于给定的开线段集合 \text{I} 和正整数 \text{k} ，计算开线段集合 \text{I} 的最长 \text{k} 可重线段集的长度。

发现和「区间集」那题没啥区别，只用关心 x 轴，换一下长度的求法…好像有点不对？因为如果存在两条线段均垂直于 x 轴，且两条线的左右端点分别都是 x_i ，这样的话，建出图来这俩线段是串在一起不交的，但是本质上应该交。

于是自然想到，要换种表示方法在 x 轴上表示一个线段。那么如果是在数轴上，比较简单的方式就是扩域。每个线段 i 的左右端点 (l_i,r_i) 变换成 (2\times l_i,2\times r_i)——听上去很不错，这样的话就相当于每个下标多了一个空间。那么对于一个左右端点相同的区间 (x,x) ，就可以连边成 (2\cdot x,2\cdot x + 1)。这样的话，原本左右端点不用的区间也要改——由于那些相同的区间右端点加了 1，所以如果存在这样两个线段 (p,p) 、 (p,q) ，那么原本不交的两个区间，在扩域之后变成了相交的 (2p,2p+1)、(2p,2q) 。

处理方式很简单，对于一个 p\not=q 的区间 (p,q)，连边 (2p+1,2q) 即可。思考这么做为啥是对的。对于原本存在的两个均不垂直 x 轴的线段，他们如果相交，那么交的那一端，r_1-l_2\geq 1 ；如果不交，那么有 l_2-r_1\geq 1 。扩域之后就变成了 \geq 2 。所以如果只是左端点增加 1 ，根本不影响判定。

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

int calc(int a, int b, int c, int d){
    return (int)sqrt((ll)(a - c) * (a - c) + (ll)(b - d) * (b - d)) ;
}
int main(){
    int a, b, c, d ;
    cin >> _n >> _k ; cnt = -1 ;
    memset(head, -1, sizeof(head)) ;
    for (int i = 1 ; i <= _n ; ++ i){
        cin >> a >> b >> c >> d ;
        len[i] = calc(a, b, c, d) ;
        base[i].ft = a << 1 ;
        base[i].sc = c << 1 ;
        if (a == c)
            ++ base[i].sc ;
        else ++ 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 ;
}