题意：平面内最多26个点，给出一些点与点之间的矛盾关系，问最少使用多少颜色才能给这些点染色，并保证矛盾点之间不同色。
分析：深搜，对于每个点先尝试已经给别的点染过的颜色，如果不行再尝试染新的颜色，注意新的颜色只需要尝试一次即可，因为各种新的颜色对于当前状态来说是等价的。
View Code #include#include #include #include using namespace std;#define maxn 30#define maxm maxn * maxn#define maxl maxn + 2#define inf 0x3f3f3f3fstruct Edge{ int v, next;}edge[maxm];int head[maxn];int color[maxn];int n;int edge_cnt;int ans;void addedge(int a, int b){ edge[edge_cnt].v = b; edge[edge_cnt].next = head[a]; head[a] = edge_cnt++;}void input(){ edge_cnt = 0; memset(head, -1, sizeof(head)); char st[maxl]; for (int i = 0; i < n; i++) { scanf("%s", st); int len = strlen(st); for (int j = 2; j < len; j++) { addedge(i, st[j] - 'A'); addedge(st[j] - 'A', i); } }}bool ok(int a){ for (int i = head[a]; ~i; i = edge[i].next) if (color[a] == color[edge[i].v]) return false; return true;}void dfs(int color_num, int a){ if (a == n) { ans = min(ans, color_num); return; } for (int i = 0; i < color_num; i++) { color[a] = i; if (ok(a)) dfs(color_num, a + 1); } color[a] = color_num; dfs(color_num + 1, a + 1); color[a] = -1;}int main(){ //freopen("t.txt", "r", stdin); while (scanf("%d", &n), n) { input(); ans = inf; memset(color, -1, sizeof(color)); dfs(0, 0); if (ans == 1) printf("1 channel needed.\n"); else printf("%d channels needed.\n", ans); } return 0;}