【解析】完美消除序列+染色[Analysis]由题知他们的关系构成一个弦图，，所以求出完美消除序列一定是成立的。先求出，然后根据序列来染色，尽可能染小的。其实时间戳那里用个线段树+二分好像也不错，甚至树状数组都可以，因为元素的变化是单调的…在此给出证明：首先进行以下的定义：团数：最大团的大小。色数：染色最少用的颜色。∵团中颜色要两两不同∴团数<=色数∵我们对序列的染色共染了t种颜色且这样的染色是合法的，但是暂时不能保证最少。∴t>=色数。又∵我们的染色方法是贪心的，遇到团的最后一个元素染色最大∴t=团数。∴团数>=色数，团数<=色数∴团数=色数。∴t=团数=色数，证毕。ppt中O(n+m)的实现很多都没讲清楚，戳这里可以看MCS的实现：。[Sum]①弦图的团数=色数。②完美消除序列的三种求法：暴力，优先队列，线性。③如果要更改队列里的元素，等价于重新在插入元素，这样原来队列里的元素不会产生影响。在优先队列、链表等多种数据结构中用到。④记录时间戳染色的方法。[Code]优先队列**************************************************************Problem: 1006User: y20070316Language: C++Result: AcceptedTime:848 msMemory:28960 kb****************************************************************/ #include <cstdio>#include <cstring>#include <cstdlib>#include <queue>using namespace std; const int N=10001;const int M=1000001; struct G{int v,nxt;}map[M+M];int tt,hd[N]; //Graphint lab[N],tid[N],seq[N];int color[N],r[N],colornum;int n,m;struct node{int w,id;friend bool operator<(node a,node b){return a.w<b.w;}};priority_queue<node> q; inline int read(void){int s=0,f=1; char c=getchar();for (;c<'0'||c>'9';c=getchar());for (;'0'<=c&&c<='9';c=getchar()) s=s*10+c-48;return s*f;} inline void ins(int u,int v){map[++tt].v=v;map[tt].nxt=hd[u];hd[u]=tt;} void init_graph(void){int x,y;n=read(),m=read();for (int i=1;i<=m;i++){x=read(),y=read();ins(x,y),ins(y,x);}} void get_queue(void){node t;for (int i=1;i<=n;i++){t.id=i,t.w=lab[i];q.push(t);}for (int num=n;num>0;num–){for (;!q.empty();){t=q.top(),q.pop();if (!tid[t.id]) break;}seq[num]=t.id,tid[t.id]=num;for (int k=hd[t.id];k;k=map[k].nxt)if (!tid[map[k].v]){lab[map[k].v]++;t.id=map[k].v;t.w=lab[map[k].v];q.push(t);}}} void color_graph(void){int now;for (int num=n;num>0;num–){now=seq[num];for (int k=hd[now];k;k=map[k].nxt)if (tid[map[k].v]>num) r[color[map[k].v]]=now;int d=0;for (int k=1;k<=colornum;k++)if (r[k]^now){color[now]=k;d=1; break;}if (!d) color[now]=++colornum;}printf("%d\n",colornum);} int main(void){init_graph();get_queue();color_graph();return 0;}</span>
[Code]链表
<span style="font-size:18px;">/**************************************************************Problem: 1006User: y20070316Language: C++Result: AcceptedTime:484 msMemory:24596 kb****************************************************************/ #include <cstdio>#include <cstring>#include <cstdlib>#include <queue>using namespace std; const int N=10001;const int M=1000001; struct G{int v,nxt;}map[M+M];int tt,hd[N]; //Graphint lab[N],tid[N],seq[N];int color[N],r[N],colornum;int n,m;G list[N+M]; int mxf,lhd[N],tl; //List for MCS inline int read(void){int s=0,f=1; char c=getchar();for (;c<'0'||c>'9';c=getchar());for (;'0'<=c&&c<='9';c=getchar()) s=s*10+c-48;return s*f;} inline void insg(int u,int v){map[++tt].v=v;map[tt].nxt=hd[u];hd[u]=tt;} void init_graph(void){int x,y;n=read(),m=read();for (int i=1;i<=m;i++){x=read(),y=read();insg(x,y),insg(y,x);}} inline void inslist(int floor,int id){list[++tl].v=id;list[tl].nxt=lhd[floor];lhd[floor]=tl;} void get_queue(void){int now;for (int i=1;i<=n;i++) inslist(lab[i],i);for (int num=n;num>0;num–){for (;tid[list[lhd[mxf]].v];){lhd[mxf]=list[lhd[mxf]].nxt;if (!lhd[mxf]) mxf–;}now=list[lhd[mxf]].v; lhd[mxf]=list[lhd[mxf]].nxt;for (;!lhd[mxf];) mxf–;tid[now]=num,seq[num]=now;for (int k=hd[now];k;k=map[k].nxt)if (!tid[map[k].v]){lab[map[k].v]++;if (lab[map[k].v]>mxf) mxf=lab[map[k].v];inslist(lab[map[k].v],map[k].v);}}} void color_graph(void){int now;for (int num=n;num>0;num–){now=seq[num];for (int k=hd[now];k;k=map[k].nxt)if (tid[map[k].v]>num) r[color[map[k].v]]=now;int d=0;for (int k=1;k<=colornum;k++)if (r[k]^now){color[now]=k;d=1; break;}if (!d) color[now]=++colornum;}printf("%d\n",colornum);} int main(void){init_graph();get_queue();color_graph();return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
我要准备好行李启程了，谢谢关心我的家人和朋友，
