【問題描述】
n個人在做傳遞物品的游戲,編號為1-n。
游戲規(guī)則是這樣的：開始時物品可以在任意一人手上，他可把物品傳遞給其他人中的任意一位；下一個人可以傳遞給未接過物品的任意一人。
即物品只能經(jīng)過同一個人一次，而且每次傳遞過程都有一個代價；不同的人傳給不同的人的代價值之間沒有聯(lián)系；
求當(dāng)物品經(jīng)過所有n個人后，整個過程的總代價是多少。
【輸入】
第一行為n,表示共有n個人（16>=n>=2）；
以下為n*n的矩陣，第i+1行、第j列表示物品從編號為i的人傳遞到編號為j的人所花費的代價，特別的有第i+1行、第i列為-1（因為物品不能自己傳給自己），其他數(shù)據(jù)均為正整數(shù)(<=10000)。
(對于50%的數(shù)據(jù)，n<=11)。
【輸出】
一個數(shù)，為最小的代價總和。
【樣例輸入】
2
-1 9794
2724 –1
【樣例輸出】
2724
時間到了啊~ 明天再繼續(xù)寫。
是一個用二進(jìn)制來表示圖的狀態(tài)的動態(tài)規(guī)劃，或者說是記憶化搜索。f[i][j]中，i來表示圖的二進(jìn)制狀態(tài)，j表示這個狀態(tài)中第一個點。
1: #include <stdio.h>
2: #include <iostream>
3: #define maxn 20
4: #define MAXINT 1000000
5: using namespace std;
6:
7: int dis[maxn][maxn];
8: int n;
9: int f[70000][20];
10: int ans=MAXINT;
11:
12: int find(int a,int b)
13: {
14: if (f[a][b]!=MAXINT) return f[a][b];
15: int tem=a;
16: a-=(1<<b);
17: if (!a)
18: {
19: f[tem][b]=0;
20: return 0;
21: }
22: for (int i=0;i<n;++i)
23: if ((1<<i)&a)
24: f[tem][b]=min(find(a,i)+dis[b][i],f[tem][b]);
25: return f[tem][b];
26: }
27:
28: int main()
29: {
30: freopen("input.txt","r",stdin);
31: freopen("output.txt","w",stdout);
32:
33: scanf("%d",&n);
34: for (int i=0;i<n;++i)
35: for (int j=0;j<n;++j)
36: scanf("%d",&dis[i][j]);
37: for (int i=0;i<(1<<n);++i)
38: for (int j=0;j<n;++j)
39: f[i][j]=MAXINT;
40: for (int i=0;i<n;++i)
41: if (find((1<<n)-1,i)<ans)
42: ans=find((1<<n)-1,i);
43: printf("%d\n",ans);
44: return 0;
45: }
46: