CF1519E - Off by One
CF1519E - Off by One
题目大意
给定$n$个点$(x_i,y_i)=(\frac{a_i} {b_i},\frac{c_i} {d_i})$,求一个最大的匹配
满足匹配的点对$(x_i,y_i),(x_j,y_j)$每个点经过如下操作
$(x,y)\rightarrow (x+1,y) or (x,y+1)$
之后可能满足$\frac{y_i’} {x_i’}=\frac{y’_j} {x_j’}$
模型简化
按照$\frac{y’} {x’}$对于每个点经过两种可能变换的值分类,建立节点
我们需要决策每个$P_i$选的变换种类
显然每个斜率对应的个数为偶数时,都可以完成匹配
对于每一个$P_i$,设其两种变换之后变成的斜率对应节点为$(u,v)$,那么连一条无向边
现在问题转化为对于无向边定向,使得最少的点入度为奇数
对于任意一个连通块,若其包含奇数条边,那么至少有一个点入度为奇数
否则一定可以完成匹配
具体的,随便选择一个点作为根,然后只对于祖先向子孙的边考虑关系
从子孙向上考虑所有的边,优先让子孙的入度为偶数
那么只有包含奇数条边时,根的入度为奇数,其他节点入度永远是偶数
即达到最优解
1 |
|