题解 CF429E 【Points and Segments】

这是一道图论题。表面上不容易看出来，因为这道题目需要我们用到转化的思想。接下来我们考虑如何将它转化成一个图论模型。 ------------ 我们首先猜测如何建模。 题目要求每一个点被覆盖的线段中，红色的和蓝色的线段数量差不超过$1$，所以我们把红色边看成是$1$，蓝色边看成是$-1$，每条线段的权值是$p_i(p_i=1/-1)$，那么问题就转化成$|\displaystyle\sum p_i|\le 1$。 我们发现，$1$和$-1$是相反数，因此我们可以推断出红边和蓝边互为反向边（其实这个说法并不准确，请继续往下阅读）。那么这个边是从哪里连到哪里的呢？因为“边权”就是线段的权值，所以边就是从线段的起点连到线段的终点。 于是，我们的基本模型就出来了，那就是对于每一条线段，从线段的起点到终点连一条边，构成了一张$n$条边的**无向图**。 ------------ 接下来，我们考虑对这些边做什么。我们的目的是给线段确定一个串颜色，所以相当于是说我们要给这些线段定向。如何给这些线段定向呢？我们可以这么考虑：我们是让每一条线段从起点连向终点，相当于有两个独立的点集（左端点集合$L$和右端点集合$R$），集合内没有互相连边，集合之间互相有连边，所以实际上构成了一张二分图。那么我们对二分图中的边进行红蓝交替染色，直到染完所有的边为止。这样，我们就完成了定向。 ------------ 定向之后，我们就可以根据染色情况输出`0`或`1`。 实际上，我们并不需要初始时第一条边染什么颜色，例如`0 1 1 0 1`和`1 0 0 1 0`实际上是等价的，因此`SPJ`都会把你判为正确。 这时，我们注意到数据范围$l_i,r_i\le 10^9$（而256MB的空间储存不了$2\times 10^9$的数组），也就是说需要我们使用离散化，相当于把范围很广的一些坐标集中在$2\times n$的编号中，通过较小的编号来储存。这个在输入的时候需要特别注意。 ------------ 至此这道题就被我们完美地解决了。还有一道与本题思想类似的题目，希望大家可以触类旁通：[Codeforces 547D](https://www.luogu.org/problemnew/show/CF547D)。 下面我给出`cpp`代码： ```cpp #include<cstdio> #include<cstring> #include<vector> #include<map> using namespace std; const int MAXN=200010; vector<int>p[MAXN]; int vis[MAXN],ans[MAXN][2]; multimap<int,int>h; int tot=0; void dfs(int x,int y) { if(vis[x]>=0) return; else vis[x]=y; int sz=p[x].size(); for(int i=0;i<sz;i++) dfs(p[x][i],1^y); } int main() { memset(vis,-1,sizeof(vis)); int n;scanf("%d",&n); int l,r; for(int i=0;i<n;i++) { scanf("%d%d",&l,&r); p[i<<1].push_back(i<<1|1); p[i<<1|1].push_back(i<<1); h.insert(make_pair(l<<1,i<<1)); h.insert(make_pair(r<<1|1,i<<1|1)); } multimap<int,int>::iterator it=h.begin(); for(int i=0;i<n;i++) { int l=it->second;it++; int r=it->second;it++; p[l].push_back(r);p[r].push_back(l); } for(int i=0;i<n;i++) if(vis[i<<1]<0) dfs(i<<1,1); for(int i=0;i<n;i++) printf("%d ",vis[i<<1]); return 0; } ```