UVa 193：Graph Coloring

UVa 193：Graph Coloring2014-10-09 shuangde800 题目链接：

原题：

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

题目大意：

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

分析与总结：

URL：http://www.bianceng.cn/Programming/sjjg/201410/45673.htm

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

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

代码：

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#define MAXN 102using 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 LOCALfreopen（"input.txt","r",stdin）;#endifint 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
", 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（"
"）;}return 0;}