BZOJ 1006: [HNOI2008]神奇的国度 弦图学习笔记

题目

1006: [HNOI2008]神奇的国度

题解

挺裸的弦图。。但是我没有学过，幸好及时查了题解

其实是问一个弦图的最少染色方案。

cdq的论文（前面关于定义的部分可以跳过直接看35和59）告诉我们，弦图染色是从完美消除序列倒着染色，每次取mex（意会即可，最小的没出现的颜色），就可以了。其实这一步是可以暴力做的，不要以为复杂度是$n^2$噢,其实是$n+m$,详见代码。

剩下的就是找一个完美消除序列了。cdq论文里说，可以用最大势算法。
所以我主要是讲实现。。我觉得可能很多跟我一样的萌新不懂怎么做到$n+m$只会用堆。（其实这题暴力找最大的好像也就，1400ms?）

每个点一个vis，表示染色没有。然后开n个队列（其实这一步手写链表也是ok的，不过，，队列好写），q[i]表示第i个队列，每次要把某个点的势+1的时候，如果原来的势是x，那么就把它扔进q[x+1]，不用删除，顺便用一个变量记录一下最大的势。然后取点的时候就从最大的势的队列里面取，如果vis为真就扔掉，如果空了就 - -（减减） 最大的势，继续做，就能找到了。时间复杂度也很好算的。总势数，，大概跟m同阶。

另外就是，找到完美消除序列之后，要倒着染色。而最大势算法刚好是倒着标号的。所以就正了，，千万别像我一样以为染色是正着的。（不好好看ppt的危害）

代码

感觉这题$n+m$就比$n^2$小个常数。
这是暴力最大势的算法：http://blog.csdn.net/just_sort/article/details/54588449 1400ms
我的 600ms

//QWsin
#include<cmath>
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;inline int read(){int ret=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';return ret; 
}const int maxn=10000+10;
const int maxm=2000000+10;int n,m;int first[maxn],next[maxm],v[maxm],ecnt;
inline void add_edge(int u,int V){next[ecnt]=first[u];first[u]=ecnt;v[ecnt++]=V;next[ecnt]=first[V];first[V]=ecnt;v[ecnt++]=u;
}inline void init_data()
{cin>>n>>m; memset(first,-1,sizeof first);for(int i=1;i<=m;++i) add_edge(read(),read());
}int SA[maxn],mx,vis[maxn],shi[maxn];
queue<int>q[maxn];inline void MCS()
{mx=0;shi[0]=-1;for(int i=1;i<=n;++i) q[0].push(i),shi[i]=0;for(int o=1;o<=n;++o)   {while(1){while(!q[mx].size()) --mx;int t=q[mx].front();q[mx].pop();if(!vis[t]) {SA[o]=t;vis[t]=1;for(int i=first[t];i!=-1;i=next[i])if(!vis[v[i]]){q[++shi[v[i]]].push(v[i]);  mx=max(mx,shi[v[i]]);}break;}}}
}int col[maxn],ans=0;
inline void color()
{//弦图染色要从后往前 memset(vis,0,sizeof vis);for(int o=1;o<=n;++o){for(int i=first[SA[o]];i!=-1;i=next[i]) vis[col[v[i]]]=o;for(int i=1;i<=n;++i) if(vis[i]!=o) {col[SA[o]]=i;ans=max(ans,i);break;}}cout<<ans;
}int main()
{init_data();MCS();color();return 0;
}