旅行售货员问题
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.样例输入：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
25 81 2 51 4 71 5 92 3 102 4 32 5 63 4 84 5 43 11 2 10 |
5.样例输出：
|
1
2
|
Case 1: 36Case 2: -1 |
6.解决方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
//旅行售货员问题 （回溯）#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
2
3
4
5
6
7
8
9
10
|
15 8 51 21 31 42 32 42 53 44 5 |
5.样例输出：
|
1
|
Case 1: 360 |
6.解决方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#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; //输入测试个数 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;} |
