首页 > 其他 > 详细

BZOJ 1006 神奇的国度

时间:2019-12-08 10:37:38      阅读:99      评论:0      收藏:0      [点我收藏+]

题面

题意

??给出弦图,求最小染色数。

题解

??先用 MCS 算法求出完美消除序列,再从完美消除序列倒序贪心给每个结点染上相邻结点还没染上的最小的颜色。复杂度 \(O(n+m)\)


代码

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e4+5,maxm=2e6+5;
namespace G { int hea[maxn],nex[maxm],to[maxm],tot; }
inline int read(){
    int ans=0;
    char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9'){
        ans=ans*10+ch-'0'; ch=getchar();
    }
    return ans;
}
void add(int u,int v){
    using namespace G;
    tot++;
    nex[tot]=hea[u];
    hea[u]=tot;
    to[tot]=v;
}
int arr[maxn],val[maxn],col[maxn],tag;
bool vis[maxn];
namespace H { int hea[maxn],bef[maxn],nex[maxn]; }
int n,m;
void erase(int u){
    using namespace H;
    int v=bef[u],w=nex[u];
    if (v) nex[v]=w;
    else hea[val[u]]=w;
    if (w) bef[w]=v;
}
void add(int u){
    using namespace H;
    int h=val[u];
    nex[u]=hea[h];
    hea[h]=u;
    bef[u]=0;
    if (nex[u]) bef[nex[u]]=u;
}
void get(){
    using namespace G;
    int i,u,v,ed,tot;
    for (i=1;i<=n;i++){
        val[i]=1; add(i);
    }
    tag=1; tot=0;
    while (true){
        while (tag&&!H::hea[tag]) tag--;
        if (!tag) break;
        u=H::hea[tag]; erase(u); val[u]=0; arr[tot++]=u;
        for (ed=hea[u];ed;ed=nex[ed]) if (val[v=to[ed]]){
            erase(v); tag=max(tag,++val[v]); add(v);
        }
    }
}
void solve(){
    using namespace G;
    int i,u,v,ed;
    for (i=1;i<=n;i++) vis[i]=false;
    for (i=0;i<n;i++){
        u=arr[i];
        for (ed=hea[u];ed;ed=nex[ed]) vis[col[to[ed]]]=true;
        col[u]=1;
        while (vis[col[u]]) col[u]++;
        for (ed=hea[u];ed;ed=nex[ed]) vis[col[to[ed]]]=false;
    }
}
int main(){
    int i,u,v;
    int ans;
    n=read(); m=read();
    for (i=0;i<m;i++){
        u=read(); v=read();
        add(u,v); add(v,u);
    }
    get();
    solve();
    ans=0;
    for (i=1;i<=n;i++) ans=max(ans,col[i]);
    printf("%d\n",ans);
    return 0;
}

BZOJ 1006 神奇的国度

原文:https://www.cnblogs.com/Kilo-5723/p/12004368.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!