自动搬运

查看原文

来自洛谷，原作者为

	皎月半洒花 在那之前，你要多想。

搬运于2025-08-24 21:48:05，当前版本为作者最后更新于2020-03-18 08:34:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

喷的原因可以去看我的上一篇题解: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}$ 可重线段集的长度。

$1\leq n\leq500,$ $1 \leq k \leq 13$.

发现和「区间集」那题没啥区别，只用关心 $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 ;
}