UVa 193：Graph Coloring

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=129

原题：

You are to write a program that tries to find an optimal coloring for a given graph. Colors are applied to the nodes of the graph and the only available colors are black and white. The coloring of the graph is called optimal if a maximum of nodes is black. The coloring is restricted by the rule that no two connected nodes may be black.

Figure: An optimal graph with three black nodes

题目大意：

给一张图染色， 只能染白色或黑色， 不能让相连的两个点都是染成黑色（白色的可以）。 求这张图能染黑色的最多点数

分析与总结：

其实就是对于每一个点，染黑，或者不染黑的问题。直接暴力搜索即可。

参考：王晓东的《计算机算法设计与分析第三版》P163页 ”图的m着色问题“。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 102
using namespace std;
int n,k, G[MAXN][MAXN], maxVal;
int color[MAXN], ans[MAXN];  

// 判断与这个点相连的是否有黑色的
inline bool isOk(int u){
    for(int i=1; i<=n; ++i)
        if(G[u][i] && color[i])return false;
    return true;
}  

void search(int u, int num){
    if(u > n){
        if(num > maxVal){
            maxVal = num;
            memcpy(ans, color, sizeof(ans)) ;
        }
        return;
    }
    if(num + n - u + 1 <= maxVal) return;// 减枝
    if(isOk(u)){
        color[u] = 1;
        search(u+1, num+1);
        color[u] = 0;
    }
    search(u+1, num);
}  

int main(){
#ifdef LOCAL
    freopen("input.txt","r",stdin);
#endif
    int T, u, v;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d", &n, &k);
        memset(G, 0, sizeof(G));
        for(int i=0; i<k; ++i){
            scanf("%d %d", &u, &v);
            G[u][v] = G[v][u] = 1;
        }  

        maxVal = -2147483646;  

        memset(color, 0, sizeof(color));
        search(1, 0);  

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

        bool flag=true;
        for(int i=1; i<=n; ++i)if(ans[i]){
            if(flag){ printf("%d",i);  flag=false;}
            else printf(" %d",i);
        }
        printf("\n");
    }
    return 0;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索include
， 图的m着色问题
， nodes
， graph
， black
， 黑色
The
coloring book、coloring、coloring book aac、food coloring、coloring pages，以便于您获取更多的相关知识。