【CODEVS】2800 送外卖

【算法】最短路(floyd)+状态压缩型动态规划

【题解】

经典的TSP问题(货郎担问题)：求最小权哈密顿回路(遍历全图点一次且仅一次)。本题稍作改动，先说原TSP问题解法：状压DP。

状态用二进制表示每个点是否走过（状态也包括最后走的点），状态转移关键在于每个点都有且只有另一个点指向它，所以先可以枚举状态k(按顺序枚举时，后面集合的子集已经全部计算完毕)，

对于每个状态枚举最后到达的节点i，再枚举i的所有邻边节点j，从恰好缺i且最后节点为j的状态转移过来。

memset(f,0x3f,sizeof(f));//初始化为正无穷

f[][]=;//不算起点

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

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

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

   if((<<(i-))&k)f[i][k]=min(f[i][k],f[j][k-(<<(i-))]+mp[j][i]);

printf("%d",f[][(<<n)-]);

这里有一个细节，设初始状态为f[1][0]=0（起点为1），即起点的初态不包含自身，那么最后f[1][(1<<n)-1]就是答案。

那么这道题的修改主要是一个城市可以经过多次，那么先跑一遍floyd得出两城市间最短距离后就不必再纠结重复经过的事了。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=;

int n,mp[maxn][maxn],f[maxn][];

int main()

{

    scanf("%d",&n);n++;

    int x;

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

     {

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

          {

              scanf("%d",&x);

              mp[i][j]=x;

          }

     }

    for(int i=;i<=n;i++)mp[i][i]=;

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

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

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

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

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

    f[][]=;

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

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

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

       if((<<(i-))&k)f[i][k]=min(f[i][k],f[j][k-(<<(i-))]+mp[j][i]);

    printf("%d",f[][(<<n)-]);

    return ;

}

巴特西

【CODEVS】2800 送外卖

最新文章

热门文章