2022秋季《人工智能》_EOJ E.地图染色

题目

思路

遍历所有合法的染色情况，找出色数最小的

代码

#include <bits/stdc++.h>
#define MAXN 30using namespace std;int n, m;
int edge[MAXN][MAXN]={
    {
    0}};  // 边表
bool book[MAXN]={
    0};  // 点是否被染过色
// colorsCanUse[i][j]：点i是否能用颜色j
//bool colorsCanUse[MAXN][MAXN];
//int colorOfPoint[MAXN];
int colorNum=0;  // 当前到哪个颜色
int finalColorNum=MAXN+1;
int finalColorOfPoint[MAXN];typedef struct
{
    int num;  // 邻域中点的个数int idx;
// vector<int> v; // 邻居
}nodeNeighbor;nodeNeighbor neighbor[MAXN];bool myCmp(nodeNeighbor a,nodeNeighbor b)
{
    return a.num>b.num;
}// 计算每个点的邻域，并按邻居个数降序排序
void calculateNeighbor()
{
    for(int i=0;i<n;i++){
    int cnt=0;  // 求解每个点的相邻边数for(int j=0;j<n;j++){
    cnt+=edge[i][j];}neighbor[i].num=cnt;neighbor[i].idx=i;}sort(neighbor,neighbor+n,myCmp);
}// 获得mcv
int calculateMCV()
{
    int i=0;while(i<n&&book[neighbor[i].idx])i++;return neighbor[i].idx;
}// 检查是否所有点都已被上色
bool isAllPointsColored()
{
    for(int i=0;i<n;i++){
    if(book[i]==false)return false;}return true;
}// 递归寻找染色情况
// 每得到一个合法的染色情况时，比较当前情况是否更优
void propagate(int node, int color, int colorOfPoint[MAXN], bool colorsCanUse[MAXN][MAXN])
{
    // 注意相等情况也可直接跳过if(color>=finalColorNum){
    return;}// 获得一个合法染色，判断是否更优if(isAllPointsColored()){
    // 获得当前色数int* maxEle=max_element(colorOfPoint,colorOfPoint+n);colorNum=*maxEle;if(colorNum<finalColorNum){
    finalColorNum=colorNum;for(int i=0;i<n;i++)finalColorOfPoint[i]=colorOfPoint[i];}return;}// 如果使用全局变量，每次递归结束返回时都无法恢复原数组// 作为colorOfPoint的临时变量，用作传参int tmp[MAXN]={
    0};for(int i=0;i<n;i++)tmp[i]=colorOfPoint[i];// 作为colorsCanUse的临时变量，用作传参bool tmp1[MAXN][MAXN];for(int i=0;i<n;i++){
    for(int j=0;j<n;j++)tmp1[i][j]=colorsCanUse[i][j];}// 处理邻域
// for(int i=0;i<neighbor[node].num;i++)
// {
    
// tmp1[neighbor[node].v[i]][color]=false;
// }for(int i=0;i<n;i++){
    if(edge[node][i])tmp1[i][color]=false;}// 选定下一个染色的点int mcv=calculateMCV();
// cout<<"mcv"<<mcv<<endl;int currentColor=0;for(;currentColor<n;currentColor++){
    if(tmp1[mcv][currentColor]==true){
    book[mcv]=true;tmp[mcv]=currentColor;propagate(mcv,currentColor,tmp,tmp1);// 恢复bookbook[mcv]=false;// 不可省略，否则每次都会进入直接被返回的递归if(currentColor>=finalColorNum)return;}}}int main()
{
    cin>>n>>m;for(int i=0;i<m;i++){
    int u,v; cin>>u>>v;edge[u][v]=edge[v][u]=1;}bool colorsCanUse[MAXN][MAXN];for(int i=0;i<n;i++){
    for(int j=0;j<n;j++)colorsCanUse[i][j]=true;}calculateNeighbor();int mcv=calculateMCV();
// cout<<"mcv"<<mcv<<endl;int colorOfPoint[MAXN];for(int i=0;i<n;i++)colorOfPoint[i]=-1;colorOfPoint[mcv]=colorNum;book[mcv]=true;propagate(mcv,colorNum,colorOfPoint,colorsCanUse);cout<<finalColorNum+1<<endl;for(int i=0;i<n;i++)cout<<finalColorOfPoint[i]<<endl;return 0;
}