主题连接：

id=3311">http://poj.org/problem?id=3311

题目大意：有n+1个点,给出点0~n的每两个点之间的距离，求这个图上TSP问题的最小解

思路：用二进制数来表示訪问过的城市集合。f[{S}][j]=已经訪问过的城市集合为S，訪问了j个城市。所需的最少花费。

这里提一下二进制数表示集合的方法（这里最好还是设集合中最多有n个元素）：

假设集合S中最多会出现n个元素，则用长度为n的二进制数来表示集合S，每一位代表一个元素。该位为0表示该元素在集合S中不存在，为1表示该元素在集合S中存在

位数 4 3 2 1

S     1 0 1 1

这个集合S里有元素1、2、4

以下是二进制数表示几种集合运算的方法

1、集合S的全集U=(1<<n)-1

2、检查集合S中是否含元素i   S&(1<<(i-1))   (返回0表示不存在。返回1表示存在)

3、从集合S中去除元素i S^(1<<(i-1))

以下是本题的思路：

首先对整个图跑一次Floyd多源最短路。得到两两点之间的最短距离，然后用DP求解，f[{S}][j]=已经訪问过的城市集合为S。訪问了j个城市，所需的最少花费。

f[S][i]=min{f[S-{j}][j]+dist[j][i]}

最后得到的答案ans=min(f[全集][i]+dist[i][0])

代码：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

#define MAXN 15

#define MAXM 1<<15

#define INF 0x3f3f3f3f

using namespace std;

int f[MAXM][MAXN]; //f[{S}][j]=已经訪问过的城市集合为S。訪问了j个城市，所需的最少花费

int dist[MAXN][MAXN]; //点与点之间的距离

int n;

int min(int a,int b)

{

    if(a<b) return a;

    return b;

}

void Floyd()

{

    for(int k=0;k<=n;k++)

        for(int i=0;i<=n;i++)

            for(int j=0;j<=n;j++)

                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

}

int TSP() //DP求TSP

{

    memset(f,0x7f,sizeof(f));

    for(int s=0;s<(1<<n);s++) //枚举訪问城市集合S，全集为(1<<n)-1

        for(int i=1;i<=n;i++) //枚举近期訪问过的城市i

            if(s&(1<<(i-1))) //city(i)∈S

            {

                if(s==(1<<(i-1))) //{city(i)}==S

                    f[s][i]=dist[0][i];

                else

                {

                    for(int j=1;j<=n;j++) //枚举上一次訪问的城市j

                    if((s&(1<<(j-1)))&&i!=j) //城市j不和i同样

                        f[s][i]=min(f[s][i],f[s^(1<<(i-1))][j]+dist[j][i]); //Cs {city(J)}=s^(1<<(i-1))

                }

            }

    int ans=INF;

    for(int i=1;i<=n;i++)

        ans=min(ans,f[(1<<n)-1][i]+dist[i][0]);

    return ans;

}

int main()

{

    while(scanf("%d",&n)&&n)

    {

        memset(dist,0,sizeof(dist));

        for(int i=0;i<=n;i++)

            for(int j=0;j<=n;j++)

                scanf("%d",&dist[i][j]);

        Floyd();

        printf("%d\n",TSP());

    }

    return 0;

}