多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

國內最全IT社區平臺 聯系我們 | 收藏本站
阿里云優惠2
您當前位置:首頁 > php開源 > 綜合技術 > BZOJ 1006 [HNOI2008]神奇的國度 弦圖的最小染色

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); }
生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關閉
程序員人生
主站蜘蛛池模板: 国产精品久久久久影视不卡 | 老司机午夜精品网站在线观看 | 欧美一区二区三区在线可观看 | 国产福利在线观看精品 | 看黄色的网址 | 久久国产大片 | 欧美第一页 | 亚洲欧美日韩人成 | 特级毛片女人18毛片 | 国产一区二区在线视频观看 | 91真人毛片一级在线播放 | 天堂日本 | 视频在线国产 | 一级白嫩美女毛片免费 | 久久99精品久久久久久国产越南 | 五月激情五月婷婷 | 欧美成人aⅴ | 欧美日韩亚洲一区二区精品 | 色xxxx| 欧美色图俺去了 | 波多野一区 | xxx视频在线观看免费 | 国产三级在线观看专区 | 最新中文字幕av专区 | jizz免费看| 在线91色| 小说区图片区综合久久88 | 看黄免费网站 | 日韩视频在线观看一区二区 | 亚洲天堂久久新 | 黑人性猛交xxxx乱大交一 | 人成午夜视频 | 欧美性猛交xxxx乱大交be | 国产精品短篇二区 | 欧美激情一区二区三区在线 | 综合亚洲欧美 | japanese18—23护士 | 日本特黄一级大片 | 久久久久综合国产 | 日本不卡一区视频 | 国产成人综合一区人人 |