图的m种着色方案

梦里梦外; 2022-07-11 12:11 103阅读 0赞

图的m着色  
描述 Description  
【问题描述】  
　　给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。  
【编程任务】  
　　对于给定的无向连通图G和m种不同的颜色，编程计算图的所有不同的着色法。  
【输入格式】  
　　文件color.in输入数据。第1行有3个正整数n，k 和m，表示给定的图G有n个顶点和k条边，m种颜色。顶点编号为1，2，…，n。接下来的k行中，每行有2个正整数u,v，表示图G 的一条边(u,v)。  
【输出格式】  
　　程序运行结束时，将计算出的不同的着色方案数输出到文件color.out中。  
【输入样例】  
5 8 4  
1 2  
1 3  
1 4  
2 3  
2 4  
2 5  
3 4  
4 5  
【输出样例】  
48

时间限制 Time Limitation  
各个测试点1s

map\[i,j\]生成邻接矩阵，表示无向图两点间是否能互相访问。  
color\[i\]保存各点的颜色  
//chosen\[i\]是目前可选的颜色。进行搜索。  
但chosen数组也可以去掉，因为我们可以先上色，再判断，如果不对，就不执行递归，直接回溯。判断的函数则可以直接判断周围**连接**的节点是否与已涂眼色**相同**的颜色（因为如果没连接，就算相同也不要紧；故连接了，只需保证其不相同就行，不必拿数组来存储）

代码如下：

#include<iostream>
    #include<string.h>
    using namespace std;
    int n,m;
    long long total=0;
    bool map[1001][1001];
    int color[1000];
    bool pd(int k)
    {
        for (int j=1;j<=n;j++)
        {
            if(map[k][j]==true&&color[j]==color[k])
            return false;
        }
        return true;
    }
    
    void search(int k)
    {
        if (k-1==n){
            total++;
            return;
        }
        else {
         for (int i=1;i<=m;i++)
         {
            color[k]=i;
            if (pd(k)==true) search(k+1);
            color[k]=0; 
         }   
     }
    }
    int main()
    {
        freopen("a.txt","r",stdin);
        int k;
        cin>>n>>k>>m;
        for (int i=0;i<=n;i++)
         for (int j=0;j<=n;j++)
          map[i][j]=0;
        memset(color,0,sizeof(color));
        for (int i=1;i<=k;i++)
        {
            int x,y;
            cin>>x>>y;
            map[x][y]=true;
            map[y][x]=true;
        } 
        fclose(stdin);
         search(1);
         cout<<total;
    }