frankchenfu 的博客

frankchenfu 的博客

题解 CF429E 【Points and Segments】

posted on 2018-02-11 21:10:38 | under 题解 |

这是一道图论题。表面上不容易看出来,因为这道题目需要我们用到转化的思想。接下来我们考虑如何将它转化成一个图论模型。


我们首先猜测如何建模。

题目要求每一个点被覆盖的线段中,红色的和蓝色的线段数量差不超过$1$,所以我们把红色边看成是$1$,蓝色边看成是$-1$,每条线段的权值是$p_i(p_i=1/-1)$,那么问题就转化成$|\displaystyle\sum p_i|\le 1$。

我们发现,$1$和$-1$是相反数,因此我们可以推断出红边和蓝边互为反向边(其实这个说法并不准确,请继续往下阅读)。那么这个边是从哪里连到哪里的呢?因为“边权”就是线段的权值,所以边就是从线段的起点连到线段的终点。

于是,我们的基本模型就出来了,那就是对于每一条线段,从线段的起点到终点连一条边,构成了一张$n$条边的无向图


接下来,我们考虑对这些边做什么。我们的目的是给线段确定一个串颜色,所以相当于是说我们要给这些线段定向。如何给这些线段定向呢?我们可以这么考虑:我们是让每一条线段从起点连向终点,相当于有两个独立的点集(左端点集合$L$和右端点集合$R$),集合内没有互相连边,集合之间互相有连边,所以实际上构成了一张二分图。那么我们对二分图中的边进行红蓝交替染色,直到染完所有的边为止。这样,我们就完成了定向。


定向之后,我们就可以根据染色情况输出01

实际上,我们并不需要初始时第一条边染什么颜色,例如0 1 1 0 11 0 0 1 0实际上是等价的,因此SPJ都会把你判为正确。

这时,我们注意到数据范围$l_i,r_i\le 10^9$(而256MB的空间储存不了$2\times 10^9$的数组),也就是说需要我们使用离散化,相当于把范围很广的一些坐标集中在$2\times n$的编号中,通过较小的编号来储存。这个在输入的时候需要特别注意。


至此这道题就被我们完美地解决了。还有一道与本题思想类似的题目,希望大家可以触类旁通:Codeforces 547D

下面我给出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;
}