坐牢,一道不会,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