李道强-6分.txt

这是很不错的计算机算法

#include <iostream>
#include <fstream.h>

class Color{
  friend int mColoring(int,int,int **);
  private:
    bool Ok(int k);
    void Backtrack(int t);
    int n,m,**a,*x;
    long 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);
	    //x[t]=0;
    }
}

bool Color::Ok(int k)
{
  //for (int j=1;j<=n;j++)// 检查颜色可用性
  for (int j=1;j<=k;j++)
    if ((a[k][j]==1)&&(x[j]==x[k])) return 0;
  return 1;
}

int mColoring(int n,int m,int **a)
{
	Color 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 main()
{
	int n,k,m;

  ifstream fin("input.txt");
  fin>>n>>k>>m;
  //生成邻接矩阵
  int **a=new int* [n+1];
  { int i,j;
    for(i=0;i<=n;i++)
      a[i]=new int[n+1];
    for(i=0;i<=n;i++)
      for(j=0;j<=n;j++)
        a[i][j]=0;
    while((k--)>0){
    	fin>>i>>j;
    	a[i][j]=a[j][i]=1;
    }
  }
  fin.close();

  int sum=mColoring(n,m,a);

  cout<<sum<<endl;
  ofstream fout("output.txt");
  fout<<sum<<endl;
  fout.close();

  { int i;
    for(i=0;i<=n;i++)
      delete[] a[i];
    delete[] a;
  }
}