首页 > 代码库 > BZOJ 1006 神奇的国度（弦图的染色数）

BZOJ 1006 神奇的国度（弦图的染色数）

2024-07-09 00:08:49   225人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1006

题意:给定一个弦图，求最小染色数。就是用最小数目的颜色进行染色使得任意两个相邻的节点颜色不同。

思路：（1）求出弦图的完美消除序列。 （2）贪心染色。从后向前用可以用的编号最小的颜色染色。在这里因为最小染色等于最大团，我直接求的最大团。为什么最小染色等于最大团呢？最大团w(G) 是包含点数最多的团,最小染色x(G)是相邻点不同色的最小颜色个数。那么w(G)<=x(G)，因为最大团中起码需要w(G)种不同的颜色。对于 一个染色我们使用了T种，那么T>=x(W)；另外，T=w(G)，也就是我们只需要最大团中那么多就够了。所以w(G)=x(G)。

 

struct node{    int v,next;};node edges[N*200];int head[N],e;int n,m,a[N],d[N],h[N],q[N],p[N];void Add(int u,int v){    edges[e].v=v;    edges[e].next=head[u];    head[u]=e++;}void init(){    int i,j,k,t,u;    FORL1(i,n)    {        t=-1;        FOR1(j,n) if(!h[j]&&d[j]>t) t=d[j],k=j;        h[k]=1; a[i]=k; p[k]=i;        for(j=head[k];j!=-1;j=edges[j].next)        {            u=edges[j].v;            d[u]++;        }    }}int cal(){    int i,j,k,t,u,ans=0;    FORL1(i,n)    {        k=a[i]; q[k]=1;        for(j=head[k];j!=-1;j=edges[j].next)        {            u=edges[j].v;            if(p[u]>i) q[k]++;        }        ans=max(ans,q[k]);    }    return ans;}int main(){    RD(n,m);    int i,u,v;    clr(head,-1);    FOR1(i,m) RD(u,v),Add(u,v),Add(v,u);    init();    PR(cal());    return 0;}

 

 

 

 

 


联系
我们