题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=15,M=1e3+10,S=(1<<12)+10;
int n,m;

//邻接矩阵
int a[N][N],ans=INT_MAX;

//f[i][j]:表示当前最大深度为i,已经开发的宝藏屋集合为j的最小代价
int f[N][S];

//to[k]:表示点集k中的所有点最多扩展一层可以达到的的所有点(包括原来的)的集合
//dis[k][x]:x属于k扩展最多一层能到的点集,dis[k][x]表示k状态扩展到x的最短道路长度,在求to的时候可以一并求出
int to[S],dis[S][N];

//can[j]:存储所有能转移到j状态的k
//cst[j]:存储所有能转移到j状态的k的转移所需的最短道路长度之和(和can中一一对应)
vector<int> can[S],cst[S];

//非常直白的函数名啊...
inline void get_to_dis()
{
    //枚举k
    for(int k=0;k<(1<<n);k++)
    {
        to[k]=k;
        //枚举k中点
        for(int i=0;i<n;i++)
        {
            if(k&(1<<i))
            {
                //枚举可以到达的点
                for(int j=0;j<n;j++)
                {
                    if(a[i][j]==0x3f3f3f3f)continue;
                    to[k]|=(1<<j);
                    dis[k][j]=min(dis[k][j],a[i][j]);
                }
            }
        }
    }
    //时间复杂度为O((2^n)*n*n)
}

inline void get_can_cst()
{
    //枚举j
    for(int j=0;j<(1<<n);j++)
    {
        //枚举k(必须是j的子集)
        for(int k=j;k;k=(k-1)&j)
        {
            //j又要为to[k]的子集(好绕啊...)
            if((j&to[k])==j)
            {
                can[j].pb(k);
                int sum=0,s=j^k;
                for(int i=0;i<n;i++)
                {
                    if(s&(1<<i))
                    {
                        sum+=dis[k][i];
                    }
                }
                cst[j].pb(sum);
            }
        }
    }
    //时间复杂度为O((2^n)*n*n)
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        //为了方便状压,我们都减1
        scanf("%d%d%d",&u,&v,&w);
        u--;
        v--;
        a[u][v]=min(a[u][v],w);
        a[v][u]=min(a[v][u],w);
    }
    memset(dis,0x3f,sizeof(dis));
    get_to_dis();
    get_can_cst();
    memset(f,0x3f,sizeof(f));
    //初始化
    for(int i=0;i<n;i++)
    {
        f[1][(1<<i)]=0;
    }
    //枚举层
    for(int i=2;i<=n;i++)
    {
        //枚举j
        for(int j=0;j<(1<<n);j++)
        {
            //枚举所有合法的k
            for(int t=0;t<(int)can[j].size();t++)
            {
                int k=can[j][t];
                f[i][j]=min(f[i][j],f[i-1][k]+(i-1)*cst[j][t]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans=min(ans,f[i][(1<<n)-1]);
    }
    printf("%d\n",ans);
    return 0;
}