国内最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2流量王
您当前位置:首页 > php开源 > 综合技术 > BZOJ 1006 [HNOI2008]神奇的国度 弦图的最小染色

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

来源:程序员人生   发布时间:2016-03-24 08:54:53 阅读次数:745次

题意:
给定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); }
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生