首页 > 其他分享 >3.12

3.12

时间:2023-03-12 22:22:27浏览次数:31  
标签:二分 连边 3.12 绿色 T1 补图

坐牢,一道不会,T1 正解也巨难写

20 min: 看完了所有题,觉得 T1 可做(实际上也是)
2h: T1 干瞪眼
30 min: 暴力
剩余时间: T1,T3 轮流干瞪眼

T1. 挑战 NPC

昨天 T3 有个结论,原图的团大小 = n - 补图的最小点覆盖。最小点覆盖 = n - 最大匹配(二分图)。考虑怎么把问题转换为二分图。

我们很容易(bushi)想到枚举团的最长边 \((x, y)\),

那么在圆 \(x,y\) 之外的点都是不满足要求的(不然就比 \((x, y)\) 长了),所以,保留黄,绿色部分点。

容易发现如果两个点同在黄色部分或绿色的话一定有连边(弦长小于直径),所以黄色部分内部不会连边,绿色同理,所以连边只会横跨黄绿色部分(连边都是指补图)。

那么这时候做二分图匹配就行了!

实现有个小 Trick 不用写计算几何判断是黄色还是绿色,我们只需要知道他是二分图就行了,所以连完边后染色即可。

参考代码(还没写完)

标签:二分,连边,3.12,绿色,T1,补图
From: https://www.cnblogs.com/dsy-lh/p/17209396.html

相关文章