BZOJ 1006 [HNOI2008]神奇的国度 弦图的最小染色

题意: 给定一张弦图，相邻的点不同色，求需要的最少颜色个数。 解析:

解法参见CDQ的论文… 至于MCS最大势算法的O(n+m)实现办法参见金策在贴吧的留言…

对于本题来说，解法就是先求出该弦图的完美消除序列（MCS算法即可），然后因为MCS算法求出来的完美消除序列顺序是倒着的，所以我们倒着枚举每个点，寻找每个点能染得最小颜色。 MCS算法的O(n+m)实现就是我们需要维护每个点相邻有多少个点被染色，以及每个点是否被染色，以及目前最大的势是多少。 然后对于每个势的值，我们挂一个链表。 每一次在最大的势的链上查找第一位未被染色的点，，如果查到被染色的点的话，在该链上删去这个点，如果在最大的势的链上没有查到未被染色的点的话，把最大的势减1继续查即可。 选完一个点后更新这个点相邻的点的势，直接往新的势的值上挂链即可，并不需要把原来的删掉。 在这个过程同时维护最大势的值。 把如上过程重复n次。 容易证明添加删除是在O(m)复杂度下的。 所以总复杂度O(n+m)。

正确性参见CDQ论文 代码:

N 10010#define M 1000100using namespace std;int n,m;int head[N],cnt,head_link[N],cnt_link;struct node{int from,to,next;}edge[M<<2],Link[M<<2];bool vis[N];int best;void init(){memset(head,-1,sizeof(head));memset(head_link,-1,sizeof(head_link));cnt=1,cnt_link=1;}void linkadd(int from,int to){Link[cnt_link].from=from,Link[cnt_link].to=to,Link[cnt_link].next=head_link[from];head_link[from]=cnt_link++;}void edgeadd(int from,int to){edge[cnt].from=from,edge[cnt].to=to,edge[cnt].next=head[from];head[from]=cnt++;}int sta[N],height[N];int top;void getsta(){int tmp=n;while(tmp){int flag=0,choose;while(!flag){for(int i=head_link[best];i!=-1;i=Link[i].next){int to=Link[i].to;if(vis[to]){head_link[best]=Link[i].next;continue;}flag=1,vis[to]=1,choose=to;break;}if(!flag)best–;}sta[++top]=choose;for(int i=head[choose];i!=-1;i=edge[i].next){int to=edge[i].to;if(vis[to])continue;height[to]++;linkadd(height[to],to);best=max(best,height[to]);}tmp–;}}int mark[N];int color[N];int main(){init();scanf(“%d%d”,&n,&m);for(int i=1;i<=m;i++){int x,y;scanf(“%d%d”,&x,&y);edgeadd(x,y);edgeadd(y,x);}for(int i=1;i<=n;i++)linkadd(0,i);getsta();int ans=0;for(int i=1;i<=top;i++){int x=sta[i];for(int j=head[x];j!=-1;j=edge[j].next)mark[color[edge[j].to]]=i;for(int j=1;j<=n;j++){if(mark[j]==i)continue;else {color[x]=j;break;}}ans=max(ans,color[x]);}printf(“%d\n”,ans);}

快乐时，想想我的影子，我会在云上为你喝彩