【题解】[HNOI2008]神奇的国度

之前说顺着打BZOJ结果又被自己给鸽了qwq。

————————————————————————————————————

言归正传这道题应该怎么做。

先给大家普及一下弦图（连接环上俩个不相邻节点的边称为弦）和mcs算法（最小染色数=最大完全子图）的概念（会的可以直接跳代码）。

没错这题就是弦图最小涂色，直接一遍mcs就搞定了（仿佛没说一样。

将弦图分成多组的问题可以看做给弦图上的点染色且两个有直接边相连的点不能同色，这样就转化成了弦图的最小染色问题。

优先队列可以实现O(nlogn+m)的复杂度，其实还是很慢，我做这个题好几次T（真悲伤。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cctype>

#include<queue>

#define rg register

using namespace std;

inline int read(){

    rg int s=0,f=0;

    rg char ch=getchar();

    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();

    while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();

    return f?-s:s;

}

int n,m,cnt=-1;

const int MAX=2000015;

int head[MAX];

bool vis[MAX],used[MAX];

int seq[MAX],label[MAX],color[MAX];

struct edge{

    int nxt;

    int to;

}e[MAX];

void add(int u,int v){

    e[++cnt].nxt=head[u];

    e[cnt].to=v;

    head[u]=cnt;

}

typedef pair<int,int>p;

priority_queue<p>q;

void mcs(){

    for(rg int i=1;i<=n;++i) q.push(p(0,i));

    for(rg int i=n;i>=1;--i){

        while(vis[q.top().second]) q.pop();

        int u=q.top().second;

        q.pop();

        seq[i]=u;

        vis[u]=1;

        for(rg int i=head[u];~i;i=e[i].nxt){

            if(!vis[e[i].to]) q.push(p(++label[e[i].to],e[i].to));

        }

    }

}

int solve(){

    int res=0;

    for(rg int i=n;i>=1;--i){

        memset(used,0,sizeof(used));

        for(rg int j=head[seq[i]];~j;j=e[j].nxt){

            used[color[e[j].to]]=1;

        }

        for(color[seq[i]]=1;used[color[seq[i]]];++color[seq[i]]);

        res=max(res,color[seq[i]]);

    }

    return res;

}

int main(){

    memset(head,-1,sizeof(head));

    n=read(),m=read();

    for(rg int i=1;i<=m;++i){

        int u=read(),v=read();

        add(u,v);

        add(v,u);

    }

    mcs();

    printf("%d\n",solve());

    return 0;

}

巴特西

【题解】[HNOI2008]神奇的国度—BZOJ1006。

之前说顺着打BZOJ结果又被自己给鸽了qwq。

言归正传这道题应该怎么做。

先给大家普及一下弦图（连接环上俩个不相邻节点的边称为弦）和mcs算法（最小染色数=最大完全子图）的概念（会的可以直接跳代码）。

没错这题就是弦图最小涂色，直接一遍mcs就搞定了（仿佛没说一样。

将弦图分成多组的问题可以看做给弦图上的点染色且两个有直接边相连的点不能同色，这样就转化成了弦图的最小染色问题。

优先队列可以实现O(nlogn+m)的复杂度，其实还是很慢，我做这个题好几次T（真悲伤。

最新文章

热门文章