Meepo的博客

题目大意不说了，可以自己去看

点我跳转 (ﾟ▽ﾟ*)

首先这是noip考试，考场上我们要先写暴力，不仅能对拍，还能骗分。
一个显然的想法就是枚举全排列，然后暴力。
哇!70分。
传说去年报送学长一年没摸键盘敲了个枚举生成树暴力骗了90？忘了。
先不说这些废话，在我们有70分保底时，我们该去想正解了。

你发现数据范围很小，我们可以用什么状压dp？
考虑设计状态，我们肯定有一维是状态j，表示已经开发了点集为j时的最小开销，

显然不能转移，考虑加维。
考虑我们转移时还需要什么。

看题目里给的公式：\mathrm{L} \times \mathrm{K}

l是已知的，k不一定啊？
k是什么，经过点的个数？这个图是个树？
那k不就是深度？
深度最多是n？

考虑可以逐层转移。
dp[i][j]表示现在转移到第k层，开发了点的集合是j时的最小方案。
显然我们转移需要枚举在这层加入的点集。
大概就是j的补集的子集。
总复杂度和枚举子集的子集一样。
(格罗姆:那么,古尔丹,代价是什么呢?)
代价？对了，还有转移的代价如何计算？
显然我们当时读入时先存下一个最优邻接表。
然后对于一个数枚举和那个点连边即可。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int INF=7e7+5;
const int N=(1<<12)+5;

int n,m;
int mmp[15][15];
int dp[15][N],pos[N],val[15],nmb[15],res[N],tmd[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i) for(int j=0;j<n;++j) mmp[i][j]=INF;
    for(int i=1,x,y,z;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);x--;y--;
        mmp[x][y]=min(mmp[x][y],z);
        mmp[y][x]=mmp[x][y];
    }
//  for(int i=0;i<n;++i) {for(int j=0;j<n;++j) printf("%d ",mmp[i][j]);printf("\n");}
    for(int i=0;i<n;++i) pos[1<<i]=i;//pos表示二进制数所代表的节点
    memset(dp,0x3f3f3f3f,sizeof dp);
    for(int i=0;i<n;++i) dp[0][1<<i]=0;
    for(int i=0;i<n;++i)
    {
        for(int st=0;st<(1<<n);++st)
        {
            int tot=0;
            for(int k=0;k<n;++k)
            {
                if(st&(1<<k)) continue;
                val[tot]=INF;nmb[tot]=1<<k;
                for(int j=st;j;j-=j&-j)
                  val[tot]=min(val[tot],mmp[k][pos[j&-j]]*(i+1));
                tot++;
            }
            for(int j=1;j<(1<<tot);++j)
            {
                res[j]=res[j-(j&-j)]+val[pos[j&-j]];
                tmd[j]=tmd[j-(j&-j)]|nmb[pos[j&-j]];
                dp[i+1][st|tmd[j]]=min(dp[i+1][st|tmd[j]],dp[i][st]+res[j]);
            }
        }
    }
    int ans=INF;
    for(int i=0;i<=n;++i) ans=min(ans,dp[i][(1<<n)-1]);
    printf("%d\n",ans);
}