CSU1129 送货到家【状压dp】

哈哈发现这道题竟然没有题解，于是我决定写一份！

状压dp

题目：

懒惰的巫女Reimu因为各种原因在香霖堂的店主Rinnosuke那儿欠下了很多债，于是乎只好靠帮他在幻想乡中送货来偿还掉微不足道的一小部分。

懒归懒，Reimu还是很聪明的，她希望送货的总路程尽可能的短，同时任何一个地方不经过两次。

简而言之，便是在一张图上找一个边权和最小经过所有点恰好一次的封闭回路。

Input

多组输入数据。

第一行为一个N（N<=15），即图上总共有多少个点。

之后共N行以邻接矩阵格式输入边的数据。

保证i->j与j->i的距离相同。

Output

每组数据仅一行，输出最小的封闭回路或者是“NoAnswer”。

Sample Input

Sample Output

是一道很典型的旅行商问题

不同之处是，大白上的旅行商问题是一定会有答案的，而且是从0这个点开始，这道题可能会有no answer的情况并且不是从0开始

当某个图从任意点出发都无法回到起点时，就输出noanswer

因为用邻接矩阵输入，所以预处理将0设成INF表示无法连通

dp数组不能太大 20的时候就爆内存了

初始化ans为INF 跑了一圈还是INF的话说明没走通就是没结果

刚开始把每个点作为起点都判了一遍某一个无法连通的样例不知道为啥输出了结果

后来赵木杉学长启发发现因为是无向图所以并不需要判断以每个点作为起点只用判断从0开始就可以了

因为要是能形成一个圈以哪个为起点都是可以的要是不能以哪个为起点都是不行的

代码如下

#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<cstring>
#define INF 0x3f3f3f3f

using namespace std;

int n;
long long edge[20][20],dp[1<<16][16];
bool vis[20];

long long rec(int s,int v,int now)
{
    if(dp[s][v]>=0)
        return dp[s][v];

    if(s==(1<<n)-1&&v==now)
        return dp[s][v]=0;

    long long res=INF;
    for(int u=0;u<n;u++)
    {
        if(!(s>>u&1))
        {
            res=min(res,rec(s|1<<u,u,now)+edge[v][u]);
        }
    }

    return dp[s][v]=res;
}


int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                scanf("%lld",&edge[i][j]);
                if(edge[i][j]==0)
                edge[i][j]=INF;
            }
        }

        memset(dp,-1,sizeof(dp));

        int cnt=0;
        for(int i=0;i<n;i++)
        {
            if(edge[0][i]==1)
                cnt++;
        }

        long long ans=INF;
        ans=min(ans,rec(0,0,0));
        /*for(int i=0;i<n;i++)
        {
            ans=min(ans,rec(0,i,i));
        }
        */

        if(ans!=INF)
        printf("%lld
",ans);
        else
        printf("NoAnswer
");
    }
    return 0;
}

提供一组noanswer的样例吧

0 1 0 0

1 0 2 4

0 2 0 3

0 4 3 0

CSU1129 送货到家 【状压dp】

CSU1129 送货到家【状压dp】