董凌-6分.txt

这是很不错的计算机算法

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


class board
{
  private:
    
	  
	  int n;
     int m;
     int *x;
     int *bestx;
     int bestd;
     int *total;
     int *now;
     int **b;
  public:
    board(); 
    void backtrack(int i,int cd);
    void output();

};

void swap(int&,int&);


board::board()
{
  int i,j;
  ifstream fin("input.txt");
  if(fin.fail())
  {
    cout<<"input file is not exist";
   
  } 
  fin>>n>>m;
   b=new int*[n+1];

   for(i=0;i<=n;i++)
   b[i]=new int[m+1];
    
	
	
	
	for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      fin>>b[i][j];
      x=new int[n+1];

bestx=new int[n+1];
 
total=new int[m+1];
  
   now=new int[m+1];
  
  for(i=1;i<=m;i++) total[i]=now[i]=0;
  for(i=1;i<=n;i++)
  {
    x[i]=i;
    for(j=1;j<=m;j++) total[j]+=b[i][j];
  }
  bestd=m+1;
  fin.close();
}
  

void board::backtrack(int i,int cd)
{
  int j,k;
  if(i==n)
  {
    for(j=1;j<=n;j++)
      bestx[j]=x[j];
    bestd=cd;
  }
  else
    for(j=i;j<=n;j++)
    {
      int ld=0;
      for(k=1;k<=m;k++)
      {
        now[k]+=b[x[j]][k];
        if(now[k]>0&&total[k]!=now[k]) ld++;
      }
      if(cd>ld) ld=cd;
      if(ld<bestd)
      {
        swap(x[i],x[j]);
        backtrack(i+1,ld);
        swap(x[i],x[j]);
      }
      for(k=1;k<=m;k++) now[k]-=b[x[j]][k];
    }
}


void board::output()
{
  ofstream out("output.txt");
  out<<bestd<<endl;
  for(int i=1;i<=n;i++)
  {
    out<<bestx[i]<<" ";
  }
  out.close(); 
}



int main()
{
  
	
	board circuit;
	circuit.backtrack(1,0);
  circuit.output();
  return 0;
}

void swap(int& left,int& right)
{
  int temp;
  temp=left;
  left=right;
 right=temp;  
}