旅行售貨員問(wèn)題
1.問(wèn)題描述：
旅行售貨員問(wèn)題又稱TSP問(wèn)題，問(wèn)題如下：某售貨員要到若干個(gè)城市推銷商品，已知各城市之間的路程（或旅費(fèi)），他要選定一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一遍最后回到駐地的路線，使總的路線（或總的旅費(fèi)）最小。數(shù)學(xué)模型為給定一個(gè)無(wú)向圖，求遍歷每一個(gè)頂點(diǎn)一次且僅一次的一條回路，最后回到起點(diǎn)的最小花費(fèi)。
2.輸入要求：
輸入的第一行為測(cè)試樣例的個(gè)數(shù)T（ T < 120 ），接下來(lái)有T個(gè)測(cè)試樣例。每個(gè)測(cè)試樣例的第一行是無(wú)向圖的頂點(diǎn)數(shù)n、邊數(shù)m（ n < 12，m < 100 ），接下來(lái)m行，每行三個(gè)整數(shù)u、v和w，表示頂點(diǎn)u和v之間有一條權(quán)值為w的邊相連。（ 1 <= u < v <= n，w <= 1000 ）。假設(shè)起點(diǎn)（駐地）為1號(hào)頂點(diǎn)。
3.輸出要求：
對(duì)應(yīng)每個(gè)測(cè)試樣例輸出一行，格式為"Case #: W"，其中'#'表示第幾個(gè)測(cè)試樣例（從1開始計(jì)），W為TSP問(wèn)題的最優(yōu)解，如果找不到可行方案則輸出-1。
4.樣例輸入：
25 81 2 51 4 71 5 92 3 102 4 32 5 63 4 84 5 43 11 2 10
5.樣例輸出：
Case 1: 36Case 2: -1
6.解決方法：
//旅行售貨員問(wèn)題 （回溯）#include<iostream> #define N 100 using namespace std; int n,m,w, //圖的頂點(diǎn)數(shù)和邊數(shù) graph[N][N], //圖的加權(quán)鄰接矩陣 c=0, //當(dāng)前費(fèi)用 bestc=-1, //當(dāng)前最優(yōu)值 x[N], //當(dāng)前解 bestx[N]; //當(dāng)前最優(yōu)解void backtrack(int k); void swap(int &a,int &b); void swap(int &a,int &b) { int temp=a; a=b; b=temp; } void backtrack(int k) { if(k==n) { if( (c+graph[x[n-1]][x[n]]+graph[x[n]][1]<bestc||bestc==-1) && graph[x[n-1]][x[n]]!=-1 && graph[x[n]][1]!=-1 ) { bestc=c+graph[x[n-1]][x[n]]+graph[x[n]][1]; for(int i=1;i<=n;i++) { bestx[i]=x[i]; } } return ; } else { for(int i=k;i<=n;i++) { if( graph[x[k-1]][x[i]]!=-1 && (c+graph[x[k-1]][x[i]]<bestc || bestc==-1)) { swap(x[i],x[k]); c+=graph[x[k-1]][x[k]]; backtrack(k+1); c-=graph[x[k-1]][x[k]]; swap(x[i],x[k]); } } } } int main(void){ int i,j,tmp=1,testNum; cin>>testNum; while(tmp<=testNum) { cin>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=n;j++) graph[i][j]=-1; for(int k=1;k<=m;k++) { cin>>i>>j>>w; graph[i][j]=w; graph[j][i]=w; } for(i=1;i<=n;i++) { x[i]=i; bestx[i]=i; } backtrack(2); cout<<"Case "<<tmp<<": "<<bestc<<endl; bestc=-1; c=0; tmp++; } return 0;}圖的m著色問(wèn)題
1.問(wèn)題描述
給定無(wú)向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的2個(gè)頂點(diǎn)著不同顏色，求有多少種方法為圖可m著色。
2.輸入要求：
輸入的第一個(gè)為測(cè)試樣例的個(gè)數(shù)T （ T < 120 ），接下來(lái)有T個(gè)測(cè)試樣例。每個(gè)測(cè)試樣例的第一行是頂點(diǎn)數(shù)n、邊數(shù)M和可用顏色數(shù)m（ n <= 10，M < 100，m <= 7 ），接下來(lái)M行，每行兩個(gè)整數(shù)u和v，表示頂點(diǎn)u和v之間有一條邊相連。（ 1 <= u < v <= n ）。
3.輸出要求：
對(duì)應(yīng)每個(gè)測(cè)試樣例輸出兩行，第一行格式為"Case #: W"，其中'#'表示第幾個(gè)測(cè)試樣例（從1開始計(jì)），W為可m著色方案數(shù)。
4.樣例輸入：
15 8 51 21 31 42 32 42 53 44 5
5.樣例輸出：
Case 1: 360
6.解決方法：
#include<iostream>using namespace std;#define N 100int 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; //輸入測(cè)試個(gè)數(shù) while(textNum>0) { cin>>n; //輸入頂點(diǎn)個(gè)數(shù) for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]=0; cin>>M>>m; //輸入邊的個(gè)數(shù)、可用顏色數(shù) 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;}新聞熱點(diǎn)
疑難解答
圖片精選
