#include<stdio.h>
#include<iostream.h>
#include<iomanip.h>
#include<windows.h>
#include"authorInfo.h"
//////////////////////////////////
//题目：图的M着色问题 //
//题号：5_8 //
//作者：吴子桃 //
//学号：20066899 //
/////////////////////////////////
/////////////////////////////////
class Color{
friend int mColoring(int,int ,int **);
private:
bool Ok(int k);
void Backtrack(int t);
int n,//图的顶点数
m,//可用着色数
**a,//图的邻接矩阵
*x;//当前解
long sum;//当前已找到的可M着色案数
};
/////////////////////////////////
int mColoring(int n,int m,int**a)
{
Color X;
//初始化X
X.n=n;
X.m=m;
X.a=a;
X.sum=0;
int *p=new int[n+1];
for(int i=0;i<=n;i++)
p[i]=0;
X.x=p;
X.Backtrack(1);
delete []p;
return X.sum;
}
/////////////////////////////////
void Color::Backtrack(int t)
{
if (t>n) {
sum++;
for (int i=1; i<=n; i++)
cout << x[i] << ' ';
cout << endl;
}
else
for (int i=1;i<=m;i++) {
x[t]=i;
if (Ok(t)) Backtrack(t+1);
}
}
/////////////////////////////////
/////////////////////////////////
bool Color::Ok(int k)
{// 检查颜色可用性
for (int j=1;j<=n;j++)
if ((a[k][j]==1)&&(x[j]==x[k])) return false;
return true;
}
/////////////////////////////////
void main()
{
//作者信息
struct authorInfo myInfo;
myInfo.purpose="图的M着色问题";
myInfo.qustionNo="5_8";
myInfo.authorName="吴子桃";
myInfo.authorNO="20066899";
//打开输入输出文件
FILE *in,*out;
if((in=fopen("input.txt","r"))==NULL)
{ printf("cannot open infile\n");
exit(0);
}
if((out=fopen("output.txt","w"))==NULL)
{ printf("cannot open outfile\n");
exit(0);
}
showAuthorInfo(myInfo);showAuthorInfoInFile(myInfo,out);
int n,m,**a,sum;//图的顶点数，可用颜色数，图的邻接矩阵,着色方案
fscanf(in,"%d%d",&n,&m);
a=make2DArray(n,n);
cout<<"图的顶点数："<<n<<"可用颜色数："<<m<<endl;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
fscanf(in,"%d",&a[i][j]);
sum=mColoring(n,m,a);
cout<<"着色方案数为："<<sum<<"种"<<endl;
fprintf(out,"%d",sum);
system("pause");
}
