C說話應用回溯法解觀光售貨員成績與圖的m著色成績。本站提示廣大學習愛好者：（C說話應用回溯法解觀光售貨員成績與圖的m著色成績）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話應用回溯法解觀光售貨員成績與圖的m著色成績正文
觀光售貨員成績
1.成績描寫：
觀光售貨員成績又稱TSP成績，成績以下：某售貨員要到若干個城市傾銷商品，已知各城市之間的旅程（或盤費盤川），他要選定一條從駐地動身，經由每一個城市一遍最初回到駐地的道路，使總的道路（或總的盤費盤川）最小。數學模子為給定一個無向圖，求遍歷每個極點一次且僅一次的一條回路，最初回到終點的最小消費。
2.輸出請求：
輸出的第一行動測試樣例的個數T（ T < 120 ），接上去有T個測試樣例。每一個測試樣例的第一行是無向圖的極點數n、邊數m（ n < 12，m < 100 ），接上去m行，每行三個整數u、v和w，表現極點u和v之間有一條權值為w的邊相連。（ 1 <= u < v <= n，w <= 1000 ）。假定終點（駐地）為1號極點。
3.輸入請求：
對應每一個測試樣例輸入一行，格局為"Case #: W"，個中'#'表現第幾個測試樣例（從1開端計），W為TSP成績的最優解，假如找不到可行計劃則輸入-1。
4.樣例輸出：
2 5 8 1 2 5 1 4 7 1 5 9 2 3 10 2 4 3 2 5 6 3 4 8 4 5 4 3 1 1 2 10
5.樣例輸入：
Case 1: 36 Case 2: -1
6.處理辦法：
//觀光售貨員成績 （回溯）
#include<iostream>
#define N 100
using namespace std;
int n,m,w, //圖的極點數和邊數
graph[N][N], //圖的加權鄰接矩陣
c=0, //以後費用
bestc=-1, //以後最優值
x[N], //以後解
bestx[N]; //以後最優解
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著色成績
1.成績描寫
給定無向連通圖G和m種分歧的色彩。用這些色彩為圖G的各極點著色，每一個極點著一種色彩。能否有一種著色法使G中每條邊的2個極點著分歧色彩，求有若干種辦法為圖可m著色。
2.輸出請求：
輸出的第一個為測試樣例的個數T （ T < 120 ），接上去有T個測試樣例。每一個測試樣例的第一行是極點數n、邊數M和可用色彩數m（ n <= 10，M < 100，m <= 7 ），接上去M行，每行兩個整數u和v，表現極點u和v之間有一條邊相連。（ 1 <= u < v <= n ）。
3.輸入請求：
對應每一個測試樣例輸入兩行，第一行格局為"Case #: W"，個中'#'表現第幾個測試樣例（從1開端計），W為可m著色計劃數。
4.樣例輸出：
1 5 8 5 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5
5.樣例輸入：
Case 1: 360
6.處理辦法：
#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;
}
