POJ 1129-Channel Allocation（四色定理+迭代深搜） - c++编程基础

题目链接：传送门

题意：n个信号站，给出连接情况，要用信号覆盖所有信号站，要求相连的信号站不能用同一个信号。

等价问题==无向图染色==四色定理（每个平面地图都可以只用四种颜色来染色，而且没有两个邻接的区域颜色相同。已证明）

思路：深搜一条路（枚举颜色，判断当前点用已有的颜色能不能染，如不能则加一种颜色，判断强判就行了），搜到头答案就出来了。。然后返回就可以了

注意单复数。。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #define maxn 360 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1000000007 #define pp pair
               
                 #define ull unsigned long long #define max(x,y) ( ((x) > (y)) ? (x) : (y) ) #define min(x,y) ( ((x) > (y)) ? (y) : (x) ) using namespace std; int n, ans, ok, vis[28]; bool ma[28][28]; bool check(int u, int sb) { for (int i = 1; i <= n; i++) if (ma[u][i] && vis[i] == sb) { return 0; } return 1; } void dfs(int u, int s) { if (ok) { return ; } if (u == n + 1) { ans = s; ok = 1; return ; } for (int k = 1; k <= s; k++) { if (check(u, k)) { vis[u] = k; dfs(u + 1, s); } } vis[u] = ++s; dfs(u + 1, s); } int main() { char s[38]; while (scanf("%d", &n) != EOF && n) { memset(ma, 0, sizeof(ma)); memset(vis, 0, sizeof(vis)); getchar(); for (int i = 1; i <= n; i++) { scanf("%s", s); int len = strlen(s); for (int j = 2; j <= len - 1; j++) { ma[i][s[j] - 'A' + 1] = 1; ma[s[j] - 'A' + 1][i] = 1; } } ok = 0; dfs(1, 1); if (ans == 1) { puts("1 channel needed."); } else { printf("%d channels needed.\n", ans); } } return 0; }