Logo CloudLunar

CodeVS/1116

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 需要注意
四色问题 ★☆☆☆☆ 答案正确 100 2014/10/15 0:14:46 无

题意

地图相邻节点不颜色不同，共有四种颜色，求把所有点染色满的方案数。

题解

还是搜索辣，邻接矩阵转换邻接表，然后四种颜色枚举一遍。

然后有一个问题就是判重，重复的状态容易导致冗余的搜索。我们可以用二进制压位（位运算）解决这个问题。一共四种颜色加上未染色，每个节点共5种状态，所以一个点3bit即可，最多8个点需要的空间大约为1kw左右，差不多是不会爆内存的。

然后就写了个八进制位运算的类。

That's all.

代码

1116.cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<cstdio>
  2. #include<vector>
  3. #include<iostream> 
  4. class ocx
  5. {
  6.     private:
  7.         int on;
  8.     public:
  9.         ocx(int u):
  10.             on(u)
  11.         {}
  12.         void set(const int &index, const int&val)
  13.         {
  14.             on&=~(7<<(index*3));
  15.             on|=(1<<(index*3))*val;
  16.         }
  17.         void printBin()//二进制逆序输出 
  18.         {
  19.             int u=on;
  20.             std::cout<<"0b";
  21.             while(u)
  22.             {
  23.             std::cout<<u%2;
  24.             u>>=1;
  25.             }
  26.             std::cout<<std::endl;
  27.         }
  28.         const int operator [](const int &index)
  29.         {
  30.             return 7&(on>>(index*3));
  31.         }
  32.         operator int()
  33.         {
  34.             return on;
  35.         }
  36. };
  37.  
  38. int count=0;
  39. std::vector<int> map[10];
  40. int n;
  41. bool g[10000001]={}; 
  42. void dfs(const int& painted,const int& node,ocx state)
  43. {
  44.     for(int i=1;i<=4;++i)
  45.     {
  46.         bool accepted=1;
  47.         for(int j=0;j<map[node].size();++j)
  48.         {
  49.             if(state[map[node][j]]==i)
  50.             {
  51.                 accepted=0;
  52.                 break;
  53.             }
  54.         }
  55.         if(accepted)
  56.         {
  57.             state.set(node,i);
  58.             if(g[state])
  59.                 continue;
  60.             g[state]=1;
  61.             if(painted == n-1)
  62.             {
  63.                 ++count;
  64.                 continue;
  65.             }
  66.             for(int j=0;j<n;++j)
  67.             {
  68.                 if(!state[j])
  69.                 {
  70.                     dfs(painted+1,j,state);
  71.                 }
  72.             }
  73.         }
  74.     }
  75. }
  76. int main()
  77. {
  78.     std::cin>>n;
  79.     for(int i=0;i<n;++i)
  80.     {
  81.         for(int j=0;j<n;++j)
  82.         {
  83.             bool b;
  84.             std::cin>>b;
  85.             if(b)
  86.             {
  87.                 map[i].push_back(j);
  88.                 map[j].push_back(i); 
  89.             }
  90.         }
  91.     }
  92.     
  93.     dfs(0,0,0);
  94.     std::cout<<count;
  95.     return 0;
  96. }
取自“https://blog.CloudLunar.com/index.php?title=CodeVS/1116&oldid=604”
分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

著作权声明[编辑]

关于[编辑]