学步园

题意：有n个点（n<=10），m条边的图（可能有重边），问从任一点走遍整个图的最短费用和，其中每个点最多只能经过两次。

思路：tsp问题，状压dp。三进制压缩一个点已被访问的次数作为状态s，dp[s][i]代表状态s下最后一个到达的点位i的最小费用。递推方程：在dp[s][i]已计算出来的情况下，枚举下一个到达的点k，那么dp[news][k] = min{ dp[news][k]+Edge[i][k],dp[news][k] },初始化：dp为INF，dp[3的i次方][i]=0.

注意题目存在重边，因此只保留边长最小的。

两种写法，递推的效率高但顺序相对难掌握，记忆化搜索好些但效率下。

递推：

#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;

int n,m;
int tri[12],dig[59050][12];//dig[s][i]表示状态s的第i位
int dp[59050][12];
int Edge[11][11];
int ans;

void init()//初始化计算tri[i]为3的i次方和dig[s][i]
{
    tri[0]=1;
    for(int i=1;i<=10;++i) tri[i] = tri[i - 1] * 3;

    for(int s=0;s<59049;++s)
    for(int i=0,t = s;i<10;++i,t/=3) dig[s][i]=t%3;
}

void input()
{
    int a,b,c;
    memset(Edge,INF,sizeof(Edge));
    while(m--)
    {
        scanf("%d%d%d",&a,&b,&c);
        --a,--b;
        Edge[b][a]=Edge[a][b]=min(Edge[a][b],c);//存在重边，只记录边长最小的
    }
}

void getdp()
{
    memset(dp,INF,sizeof(dp));
    ans = INF;
    for(int i=0;i<n;++i) dp[ tri[i] ][i] = 0;//初始化dp边界：如果s中，仅有i被访问且只被访问一次，费用为0
    for(int s=0;s<tri[n];++s)
    {
        int vall = 1;//计算s是否每个点都访问了一遍
        for(int i=0;i<n;++i)
        {
            if(dig[s][i]==0) vall = 0;
            if(dp[s][i]==INF) continue;
            for(int k=0;k<n;++k)//枚举i所到的下一个点k
            {
                if(i == k) continue;
                if(Edge[i][k]==INF || dig[s][k]>=2) continue;//如果不存在边<i,k>或者k已被访问2次以上则不进行更新
                int news = s + tri[k];//news表示在s的基础上再访问k一次所得状态
                dp[news][k] = min(dp[news][k],dp[s][i]+Edge[i][k]);
            }
        }
        if(vall)
            for(int i=0;i<n;++i) ans = min(ans,dp[s][i]);//如果每个点都访问过，更新ans
    }
}

void getans()
{
    printf("%d\n",ans == INF? -1:ans);
}

int main()
{
    init();
    while(cin>>n>>m)
    {
        input();
        getdp();
        getans();
    }
    return 0;
}

记忆化搜索：

#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;

int n,m;
int tri[12],dig[59050][12];
int dp[59050][12];
int Edge[11][11];
int ans;

void init()
{
    tri[0]=1;
    for(int i=1;i<=10;++i) tri[i] = tri[i - 1] * 3;

    for(int s=0;s<59049;++s)
    for(int i=0,t = s;i<10;++i,t/=3) dig[s][i]=t%3;
}

void input()
{
    int a,b,c;
    memset(Edge,INF,sizeof(Edge));
    while(m--)
    {
        scanf("%d%d%d",&a,&b,&c);
        --a,--b;
        Edge[b][a]=Edge[a][b]=min(Edge[a][b],c);
    }
}

int dfs(int s,int i)
{
    if(dp[s][i]!=-1) return dp[s][i]; //体现记忆化
    int cur = INF;//初始化为INF，如果出现不合法状态会返回INF
    if(s==tri[i]) cur = 0;//如果s中，仅有i被访问且只被访问一次
    else
        if(dig[s][i])//如果i在s中确实被访问了
            for(int k=0;k<n;++k)//枚举到i的上一个点k
                    if(dig[s][k] && Edge[k][i]!=INF && k!=i)//异于i的点k必须在s中被访问过，且存在边<k，i>
                            cur = min(cur,dfs(s-tri[i],k)+Edge[k][i]);
    return dp[s][i] = cur;
}

void getdp()
{
    memset(dp,-1,sizeof(dp));
    ans = INF;

    for(int s=0;s<tri[n];++s)
        {
            int vall=1;//计算s是否每个点都访问了一遍
            for(int i=0;i<n;++i)
            {
                if(dig[s][i]==0) vall = 0;
                dfs(s,i);
            }
            if(vall) for(int i=0;i<n;++i) ans = min(ans,dp[s][i]);//如果每个点都访问过，更新ans
        }
}

void getans()
{
    printf("%d\n",ans == INF? -1:ans);
}

int main()
{
    init();
    while(cin>>n>>m)
    {
        input();
        getdp();
        getans();
    }
    return 0;
}