LibreOJ链接

Description

给出一个\(n(n\leq12)\)个点\(m(m\leq1000)\)条边的带权无向图，求该图的一棵生成树，使得其边权×该边距根的深度之和最小。

Solution

既然\(n\leq12\)，可以猜测是状压DP。

定义\(f[dpt][s][s_1]\)表示一棵深度为\(dpt\)，点集为\(s\)，最深的（深度为\(dpt\)）的点的集合为\(s_1\)的生成树的权值。我们考虑给\(s_1\)接上一些点\(s_2\)，从而转移为\(f[dpt+1][s|s_2][s_2]\)。转移方程为：$$f[dpt+1][s|s_2][s_2]=min{ f[dpt][s][s_1]+w[s_1][s_2]\times dpt } \space (s_1\in s,s_2\in \complement_U^s )$$其中\(w[s_1][s_2]\)表示将\(s_2\)接在\(s_1\)上的最小花费，预处理一下即可。

时间复杂度\(O(n\cdot 2^n \cdot 2^k 2^{n-k})=O(n4^n)\)。不过似乎有\(O(n^2 3^n)\)的做法？

Code

//「NOIP2017」宝藏

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int const N=15;

int const S=1<<12;

int const INF=0x3F3F3F3F;

int n,m,ed[N][N]; int U;

int w[S][S],f[2][S][S];

void calW()

{

    memset(w,0x3F,sizeof w);

    for(int s1=0;s1<=U;s1++) w[s1][0]=0;

    for(int s1=0;s1<=U;s1++)

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

        {

            int s2=1<<i; if(s1&s2) continue;

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

                if((s1>>j)&1) w[s1][s2]=min(w[s1][s2],ed[i+1][j+1]);

        }

    for(int s1=0;s1<=U;s1++)

        for(int s2=1;s2<=U;s2++)

        {

            if(s1&s2) continue;

            for(int i=1;i<=s2;i<<=1)

                if(s2&i) w[s1][s2]=min(w[s1][s2],w[s1][s2^i]+w[s1][i]);

        }

}

int main()

{

    scanf("%d%d",&n,&m); U=(1<<n)-1;

    if(n==1) {puts("0"); return 0;}

    memset(ed,0x3F,sizeof ed);

    for(int i=1;i<=m;i++)

    {

        int u,v,c; scanf("%d%d%d",&u,&v,&c);

        ed[u][v]=ed[v][u]=min(ed[u][v],c);

    }

    calW();

    int c=0; int ans=INF;

    memset(f,0x3F,sizeof f);

    for(int i=1;i<=U;i<<=1) f[c][i][i]=0;

    for(int dpt=1;dpt<=n;dpt++)

    {

        c^=1;

        for(int s=0;s<=U;s++)

            for(int s2=U^s;s2;s2=(s2-1)&(U^s))

            {

                int res=INF;

                for(int s1=s;s1;s1=(s1-1)&s)

                    if(f[c^1][s][s1]<INF&&w[s1][s2]<INF) res=min(res,f[c^1][s][s1]+w[s1][s2]*dpt);

                f[c][s|s2][s2]=res;

            }

        for(int s2=0;s2<=U;s2++) ans=min(ans,f[c][U][s2]);

    }

    printf("%d\n",ans);

    return 0;

}

P.S.

初始的DP数组要清\(\infty\)，而不是\(0\)。

DP数组需要滚动，否则会MLE。

我这个做法在LOJ上需要稍微卡一下常，第52行的if就是卡常用的。