【BZOJ】1006 神奇的国度

时间：2015-07-22 22:46:28 收藏：0 阅读：332

【解析】完美消除序列+染色

[Analysis]

由题知他们的关系构成一个弦图，所以求出完美消除序列一定是成立的。
先求出，然后根据序列来染色，尽可能染小的。
其实时间戳那里用个线段树+二分好像也不错，甚至树状数组都可以，因为元素的变化是单调的...

在此给出证明：

首先进行以下的定义：
团数：最大团的大小。
色数：染色最少用的颜色。

∵团中颜色要两两不同
∴团数<=色数

∵我们对序列的染色共染了t种颜色且这样的染色是合法的，但是暂时不能保证最少。
∴t>=色数。

又∵我们的染色方法是贪心的，遇到团的最后一个元素染色最大
∴t=团数。

∴团数>=色数，团数<=色数
∴团数=色数。

∴t=团数=色数，证毕。

ppt中O(n+m)的实现很多都没讲清楚，戳这里可以看MCS的实现：http://tieba.baidu.com/p/2891159900。

[Sum]
①弦图的团数=色数。
②完美消除序列的三种求法：暴力，优先队列，线性。
③如果要更改队列里的元素，等价于重新在插入元素，这样原来队列里的元素不会产生影响。
在优先队列、链表等多种数据结构中用到。
④记录时间戳染色的方法。

[Code]优先队列

**************************************************************
    Problem: 1006
    User: y20070316
    Language: C++
    Result: Accepted
    Time:848 ms
    Memory:28960 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
 
const int N=10001;
const int M=1000001;
 
struct G
{
    int v,nxt;
}map[M+M];
int tt,hd[N];   //Graph
int lab[N],tid[N],seq[N];
int color[N],r[N],colornum;
int n,m;
struct node
{
    int w,id;
    friend bool operator<(node a,node b)
    {
        return a.w<b.w;
    }
};
priority_queue<node> q;
 
inline int read(void)
{
    int s=0,f=1; char c=getchar();
    for (;c<'0'||c>'9';c=getchar());
    for (;'0'<=c&&c<='9';c=getchar()) s=s*10+c-48;
    return s*f;
}
 
inline void ins(int u,int v)
{
    map[++tt].v=v;
    map[tt].nxt=hd[u];
    hd[u]=tt;
}
 
void init_graph(void)
{
    int x,y;
    n=read(),m=read();
    for (int i=1;i<=m;i++)
    {
        x=read(),y=read();
        ins(x,y),ins(y,x);
    }
}
 
void get_queue(void)
{
    node t;
    for (int i=1;i<=n;i++)
    {
        t.id=i,t.w=lab[i];
        q.push(t);
    }
    for (int num=n;num>0;num--)
    {
        for (;!q.empty();)
        {
            t=q.top(),q.pop();
            if (!tid[t.id]) break;
        }
        seq[num]=t.id,tid[t.id]=num;
        for (int k=hd[t.id];k;k=map[k].nxt)
            if (!tid[map[k].v])
            {
                lab[map[k].v]++;
                t.id=map[k].v;
                t.w=lab[map[k].v];
                q.push(t);
            }
    }
}
 
void color_graph(void)
{
    int now;
    for (int num=n;num>0;num--)
    {
        now=seq[num];
        for (int k=hd[now];k;k=map[k].nxt)
            if (tid[map[k].v]>num) r[color[map[k].v]]=now;
        int d=0;
        for (int k=1;k<=colornum;k++)
            if (r[k]^now)
            {
                color[now]=k;
                d=1; break;
            }
        if (!d) color[now]=++colornum;
    }
    printf("%d\n",colornum);
}
 
int main(void)
{
    init_graph();
    get_queue();
    color_graph();
     
    return 0;
}</span>

[Code]链表

<span style="font-size:18px;">/**************************************************************
    Problem: 1006
    User: y20070316
    Language: C++
    Result: Accepted
    Time:484 ms
    Memory:24596 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
 
const int N=10001;
const int M=1000001;
 
struct G
{
    int v,nxt;
}map[M+M];
int tt,hd[N];   //Graph
int lab[N],tid[N],seq[N];
int color[N],r[N],colornum;
int n,m;
G list[N+M]; int mxf,lhd[N],tl; //List for MCS
 
inline int read(void)
{
    int s=0,f=1; char c=getchar();
    for (;c<'0'||c>'9';c=getchar());
    for (;'0'<=c&&c<='9';c=getchar()) s=s*10+c-48;
    return s*f;
}
 
inline void insg(int u,int v)
{
    map[++tt].v=v;
    map[tt].nxt=hd[u];
    hd[u]=tt;
}
 
void init_graph(void)
{
    int x,y;
    n=read(),m=read();
    for (int i=1;i<=m;i++)
    {
        x=read(),y=read();
        insg(x,y),insg(y,x);
    }
}
 
inline void inslist(int floor,int id)
{
    list[++tl].v=id;
    list[tl].nxt=lhd[floor];
    lhd[floor]=tl;
}
 
void get_queue(void)
{
    int now;
    for (int i=1;i<=n;i++) inslist(lab[i],i);
    for (int num=n;num>0;num--)
    {
        for (;tid[list[lhd[mxf]].v];)
        {
            lhd[mxf]=list[lhd[mxf]].nxt;
            if (!lhd[mxf]) mxf--;
        }
        now=list[lhd[mxf]].v; lhd[mxf]=list[lhd[mxf]].nxt;
        for (;!lhd[mxf];) mxf--;
        tid[now]=num,seq[num]=now;
        for (int k=hd[now];k;k=map[k].nxt)
            if (!tid[map[k].v])
            {
                lab[map[k].v]++;
                if (lab[map[k].v]>mxf) mxf=lab[map[k].v];
                inslist(lab[map[k].v],map[k].v);
            }
    }
}
 
void color_graph(void)
{
    int now;
    for (int num=n;num>0;num--)
    {
        now=seq[num];
        for (int k=hd[now];k;k=map[k].nxt)
            if (tid[map[k].v]>num) r[color[map[k].v]]=now;
        int d=0;
        for (int k=1;k<=colornum;k++)
            if (r[k]^now)
            {
                color[now]=k;
                d=1; break;
            }
        if (!d) color[now]=++colornum;
    }
    printf("%d\n",colornum);
}
 
int main(void)
{
    init_graph();
    get_queue();
    color_graph();
     
    return 0;
}

原文：http://blog.csdn.net/u013598409/article/details/47010633