UVa 193 - Graph Coloring

193-Graph Coloring

10946

22.52%

2634

58.39%

题目链接：

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;
}

—— 生命的意义，在于赋予它意义。

    

  原创http://blog.csdn.net/shuangde800，By  D_Double (转载请标明)