BZOJ 1006 [HNOI2008]神奇的国度 弦图的最小染色
来源：程序员人生 发布时间：2016-03-24 08:54:53 阅读次数：2146次
题意:
给定1张弦图，相邻的点不同色，求需要的最少色彩个数。
解析:
解法参见CDQ的论文…
至于MCS最大势算法的O(n+m)实现办法参见金策在贴吧的留言…
对本题来讲，解法就是先求出该弦图的完善消除序列（MCS算法便可），然后由于MCS算法求出来的完善消除序列顺序是倒着的，所以我们倒着枚举每一个点，寻觅每一个点能染得最小色彩。
MCS算法的O(n+m)实现就是我们需要保护每一个点相邻有多少个点被染色，和每一个点是不是被染色，和目前最大的势是多少。
然后对每一个势的值，我们挂1个链表。
每次在最大的势的链上查找第1位未被染色的点，如果查到被染色的点的话，在该链上删去这个点，如果在最大的势的链上没有查到未被染色的点的话，把最大的势减1继续查便可。
选完1个点后更新这个点相邻的点的势，直接往新的势的值上挂链便可，其实不需要把原来的删掉。
在这个进程同时保护最大势的值。
把如上进程重复n次。
容易证明添加删除是在O(m)复杂度下的。
所以总复杂度O(n+m)。
正确性参见CDQ论文
代码:
#include #include #include #include #define N 10010 #define M 1000100 using 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
",ans);
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
