题意二维平面上有\(n\)个点\((x_i,y_i)\)，你需要给每个点染色红色或蓝色使得每一行、每一列上红蓝点数差小于等于1。\(n,x_i,y_i\le2\times10^5\)。分析方法一：上下界网络流对所有行和列建点，\(x_i\rightarrowy_i\)连边，流量\([0,1]\)，有流量表示染红。源点向行点连边，流量

Description给定\(n\)个整点。你要给每个点染成红色或蓝色。要求同一水平线或垂直线上两种颜色的数量最多相差\(1\)。\(n,x_i,y_i\le2\times10^5\)。Solution考虑给每条水平线和垂直线建一个点，对于每个整点就把它对应的两条线连一条边。题目就转化为了给每条边定

CF547DMikeandFish这也能图论的一道题。思路对于\(x\)坐标相同的点，我们两两配对连边，多余的点不管。对于\(y\)坐标相同的点，我们两两配对连边，多余的点不管。这样就得到了若干个连通图，对这些连通图跑二分图染色即可得到答案。证明：由于是二分图染色，且横竖两两配对，由于连