BZOJ 1006 [HNOI2008]神奇的國度 弦圖的最小染色
來源:程序員人生 發布時間:2016-03-24 08:54:53 閱讀次數:2544次
題意:
給定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);
}
生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈