网站首页
编程语言
数据库
系统相关
其他分享
编程问答
CF547D
2024-07-24
CF547D Mike and Fish 题解
Description给定\(n\)个整点。你要给每个点染成红色或蓝色。要求同一水平线或垂直线上两种颜色的数量最多相差\(1\)。\(n,x_i,y_i\le2\times10^5\)。Solution考虑给每条水平线和垂直线建一个点,对于每个整点就把它对应的两条线连一条边。题目就转化为了给每条边定
2024-05-19
CF547D Mike and Fish
CF547DMikeandFish这也能图论的一道题。思路对于\(x\)坐标相同的点,我们两两配对连边,多余的点不管。对于\(y\)坐标相同的点,我们两两配对连边,多余的点不管。这样就得到了若干个连通图,对这些连通图跑二分图染色即可得到答案。证明:由于是二分图染色,且横竖两两配对,由于连