算法設計例題：圖的m著色（回溯） memory limit: 5000KB time limit: 2000MS accept: 8 submit: 14 Description 給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色，求有多少種方法為圖可m著色。 Input 輸入的第一個為測試樣例的個數T （ T < 120 ），接下來有T個測試樣例。每個測試樣例的第一行是頂點數n、邊數M和可用顏色數m（ n <= 10，M < 100，m <= 7 ），接下來M行，每行兩個整數u和v，表示頂點u和v之間有一條邊相連。（ 1 <= u < v <= n ）。 Output 對應每個測試樣例輸出兩行，第一行格式為"Case #: W"，其中'#'表示第幾個測試樣例（從1開始計），W為可m著色方案數。 Sample Input 1 5 8 5 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5 Sample Output Case 1: 360 Author Eapink 解決方法： #include<iostream> using namespace std; #define N 100 int m,n,M,a[N][N],x[N],textNum; int static sum=0; bool ok(int k) { for(int j=1;j<=n;j++) if(a[k][j]&&(x[j]==x[k])) return false; return true; } void 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; } } int main() { int i,j,z=1; cin>>textNum; //輸入測試個數 while(textNum>0) { cin>>n; //輸入頂點個數 for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]=0; cin>>M>>m; //輸入邊的個數、可用顏色數 for(int k=1;k<=M;k++) //生成圖的鄰接矩陣 { cin>>i>>j; a[i][j]=1; a[j][i]=1; } /* for(i=1;i<=n;i++){ for(j=1;j<=n;j++) cout<<a[i][j]<<" "; cout<<endl;}*/ for(i=0;i<=n;i++) x[i]=0; backtrack(1); cout<<"Case "<<z<<": "<<sum<<endl; sum=0; textNum--; z++; } return 0; }
