深大算法实验三——回溯法解决地图填色问题代码

#include<bits/stdc++.h> using namespace std; const int ColorNum=25; class Vec { int *Rcl; int Rnum; int No; int Slt; public: Vec() { Slt=-1; Rcl=new int[ColorNum+1]; for(int i=1; i<=ColorNum; i++) { Rcl[i]=0; } Rnum=ColorNum; } Vec &operator= (const Vec& x) { Rnum=x.Rnum; No=x.No; Slt=x.Slt; for(int i=1; i<=ColorNum; i++) { Rcl[i]=x.Rcl[i]; } return *this; } ~Vec() { delete [] Rcl; } friend class Map; }; struct SelectColor { int n; int *color; }; struct ccolor { int No; int Num; }; bool Less(const ccolor &a, const ccolor &b) { return a.Num>b.Num?1:0; } struct Degree { int edgenum; int No; int Rank; }; bool LessD(const Degree &a, const Degree &b) { return a.edgenum<b.edgenum?1:0; } class Map { long long SolutionNum; bool **arc; Vec *vec; Degree *degree; int vecN; int edgeN; int SltNum; SelectColor SltColor; int SolutionColorAdd; int *ColorCircleNum; clock_t startTime,endTime; public: Map() { SolutionNum=0; vecN=0; edgeN=0; SltNum=0; SolutionColorAdd=0; SltColor.n=ColorNum; SltColor.color=new int [ColorNum+1]; ColorCircleNum=new int [ColorNum+1]; for(int i=1; i<=ColorNum; i++) { SltColor.color[i]=0; ColorCircleNum[i]=1; } SltColor.color[0]=ColorNum; } void setVecN(int vN) { SolutionNum=0; vecN=vN; edgeN=0; arc=new bool*[vecN+1]; vec=new Vec[vecN+1]; degree=new Degree[vecN+1]; for(int i=0; i<=vecN; i++) { arc[i]=new bool[vecN+1]; arc[i][0]=true; for(int j=1; j<=vecN; j++) { arc[i][j]=0; } degree[i].edgenum=0; degree[i].No=i; vec[i].No=i; } } void setEdge(int vec1,int vec2) { arc[vec1][vec2]=1; arc[vec2][vec1]=1; degree[vec1].edgenum++; degree[vec2].edgenum++; edgeN++; } void setDegree() { sort(degree+1,degree+vecN+1,LessD); degree[0].Rank=1; for(int i=1; i<=vecN; i++) { if(degree[i].edgenum==degree[i-1].edgenum) { degree[i].Rank=degree[i-1].Rank; } else { degree[i].Rank=i; } } Degree *temp; temp=new Degree[vecN+1]; for(int i=1; i<=vecN; i++) { temp[degree[i].No].edgenum=degree[i].edgenum; temp[degree[i].No].No=degree[i].No; temp[degree[i].No].Rank=degree[i].Rank; } delete []degree; degree=temp; } bool changeR(int index,int color) { vec[index].Rnum=-1; SltNum++; for(int i=1; i<=ColorNum; i++) { if(vec[index].Rcl[i]==0) vec[index].Rcl[i]=index; } for(int i=1; i<=vecN; i++) { if(arc[index][i]==true&&vec[i].Rcl[color]==0) { if(vec[i].Rnum==1) { return false; } vec[i].Rcl[color]=index; vec[i].Rnum--; } } return true; } bool Constrain(int index) { for(int i=1; i<=vecN; i++) { if(vec[i].Rnum==1) { int cl; for(cl=1; cl<=ColorNum; cl++) //Find which Color { if(vec[i].Rcl[cl]==0) break; } vec[i].Rcl[cl]=index; vec[i].Rnum=-1; SltNum++; vec[i].Slt=cl; if(SltColor.color[cl]==0) SltColor.color[cl]=index; for(int j=1; j<=vecN; j++) { if(arc[i][j]==true&&vec[j].Rcl[cl]==0)//寻找相应连接的弧 { if(vec[j].Rnum==1) { return false; } vec[j].Rcl[cl]=index; vec[j].Rnum--; } } ChangeDegree(i); } } return true; } bool Place(int line,int color) { if(changeR(line,color)==false) { return false; } if(Constrain(line)==false) { return false; } return true; } int MRV(int line=0) { int Min=ColorNum+1; int t=1; for(int i=1; i<=vecN; i++) { if(vec[i].Rnum>0&&vec[i].Rnum<Min) { Min=vec[i].Rnum; t=i; } if(vec[i].Rnum==Min&&degree[i].Rank>degree[t].Rank) { t=i; } } return t; } void ChooseColor(int line,int &n,int *color) { n=0; ccolor *choose; choose=new ccolor[vecN]; for(int i=1; i<=ColorNum; i++) { if(vec[line].Rcl[i]==0) { choose[n].Num=ColorNum; choose[n++].No=i; } } for(int i=0; i<n; i++) { for(int j=1; j<=vecN; j++) { if(arc[line][j]==true&&vec[j].Rcl[choose[i].No]==0&&vec[j].Rnum<choose[i].Num) { choose[i].Num=vec[j].Rnum; } } } sort(choose,choose+n,Less); bool isFirst=false; int t=0; int num; for(int i=0; i<n; i++) { color[i]=choose[t++].No; if(SltColor.color[color[i]]==0&&isFirst==false) { isFirst=true; SltColor.color[color[i]]=line; num=color[i]; } if(SltColor.color[color[i]]==0&&isFirst==true) { n--; i--; ColorCircleNum[num]++; } } delete []choose; } void ChangeDegree(int index) { for(int i=1; i<=vecN; i++) { if(arc[index][i]==true) { degree[i].edgenum--; } } setDegree(); } void Backtrack(int t,int &Times) { Times++; if(SltNum>=vecN) { SolutionColorAdd=1; for(int i=1; i<=ColorNum; i++) { SolutionColorAdd*=ColorCircleNum[i]; } SolutionNum+=SolutionColorAdd; if(SolutionNum>=10000000000) { cout<<Times<<endl; endTime = clock();//记录下结束时间 cout <<" the run time is: " <<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl; exit(0); } } else { int n; int *choose; int *TempCl; TempCl=new int [ColorNum+1]; for(int i=0; i<=ColorNum; i++) { TempCl[i]=ColorCircleNum[i]; } choose=new int[ColorNum]; ChooseColor