bzoj1006: [HNOI2008]神奇的国度

弦图最小染色。MCS（最大势）算法。定理为最小染色数等于最大团（最大完全子图（任意俩个节点都有一条边相连））。

1.必须是弦图。弦图：对于任意长度大于3的环都存在弦的图。弦：连接环上俩个不相邻节点的边。

反例：比方说5边形，它的最大团的节点数为2，但需要3种颜色才能染。

2.贪心，每回选已经被染色的邻接点数目最多的节点（编号最小）染色。

反例： 1——4——3——2，染完1以后应该染4，如果染2的话，计算出的最小染色数就会为3。其实应该是2。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define val first
#define id second
using namespace std;

const int maxn = 10000 + 10;
const int maxm = 2000000 + 10;
typedef pair<int,int> Node;
priority_queue<Node> q;

int n,m,c = -1;
int h[maxn],to[maxm],next[maxm];
int seq[maxn],lable[maxn],c1[maxn];
bool vis[maxn],used[maxn];

void add(int u,int v) {
    to[++c] = v; next[c] = h[u]; h[u] = c;
    to[++c] = u; next[c] = h[v]; h[v] = c;
}

void build() {
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    for(int i = 1,a,b; i <= m; i++) {
        scanf("%d%d",&a,&b);
        add(a,b);
    }
}

void MCS() {
    for(int i = 1; i <= n; i++)
        q.push(Node(0,i));
    for(int i = n,u; i >= 1; i--) {
        while(vis[q.top().id]) q.pop();
        u = q.top().id; q.pop();
        seq[i] = u;  vis[u] = 1;
        for(int i = h[u]; ~i; i = next[i]) 
            if(!vis[to[i]]) q.push(Node(++lable[to[i]],to[i]));
    }
}

int color() {
    int res = 0;
    for(int i = n; i >= 1; i--) {
        memset(used,0,sizeof(used));
        for(int j = h[seq[i]]; ~j; j = next[j])
            used[c1[to[j]]] = 1;
        for(c1[seq[i]] = 1; used[c1[seq[i]]]; c1[seq[i]]++);
         res = max(res,c1[seq[i]]);
         //printf("c1[%d] = %d
",seq[i],c1[seq[i]]);
    }
    return res;
}

void solve() {
    MCS();
    printf("%d
",color());
}

int main() {
    build();
    solve();
    
    return 0;
}

bzoj1006: [HNOI2008]神奇的国度

相关推荐