题目链接

题目大意

给定一个 n 个点 m 条边的图，请你求出一个有根树。

满足每个点的深度和它到父节点的边权乘积之和最小。

n ≤ 12，m ≤ 1000

题目思路

本来我想的是设(dp[i][s])表示以(i)为根节点，集合为(s)的最小答案但是发现根本转移不了

考虑到点数只有12个，可以考虑状态压缩 DP。 用 s 表示当前加入的点集。

为了方便转移，我们不记录根是谁，而是直接去考虑深度。

也就是用$ dp[i][s] $表示当前的点集是 s，最深的点为 i。

然后我们去枚举 s 的补集的子集 t，把 t 都作为第 i+1 层加入 s。

我的代码复杂度为(3^n*n+2^n*n^3)

但是其实预处理(dis)数组可以一次预处理出来，而我处理了(n)次，可以再优化一点

代码

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=12+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,m;
int e[maxn][maxn];
int dis[maxn];
int dp[maxn][1<<12];
signed main(){
    scanf("%d%d",&n,&m);
    memset(e,0x3f,sizeof(e));
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        u--,v--;
        e[v][u]=min(e[v][u],w);
        e[u][v]=e[v][u];
    }
    memset(dp,0x3f,sizeof(dp));
    for(int i=0;i<=n-1;i++){
        dp[0][1<<i]=0;
    }
    for(int i=0;i<=n-2;i++){
        for(int sta=0;sta<=(1<<n)-1;sta++){
            if(dp[i][sta]==inf) continue;
            for(int j=0;j<n;j++){
                dis[j]=inf;
                for(int k=0;k<n;k++){
                    if(sta&(1<<k)){
                        dis[j]=min(dis[j],e[j][k]);
                    }
                }
            }
            int zi=(((1<<n)-1)^sta);
            for(int j=zi;;j=((j-1)&zi)){
                int sum=0;
                for(int k=0;k<n;k++){
                    if(j&(1<<k)){
                        sum+=dis[k];
                    }
                    if(sum>=inf) break;
                }
                if(sum<inf){
                    dp[i+1][sta|j]=min(dp[i+1][sta|j],dp[i][sta]+sum*(i+1));
                }
                if(!j) break;
            }
        }
    }
    int ans=inf;
    for(int i=0;i<=n-1;i++){
        ans=min(ans,dp[i][(1<<n)-1]);
    }
    printf("%d
",ans);
    return 0;
}