题解 P3357 【最长k可重线段集问题】
皎月半洒花
2020-03-18 08:34:29
感觉这题压根没有正常的题解啊……
喷的原因可以去看我的上一篇题解:[P3358Sol 戳我](https://www.luogu.com.cn/blog/pks-LOVING/solution-p3358)
由于这题需要用到 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$ ，根本不影响判定。
```cpp
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 ;
}
```