[LUOGU] 3959 宝藏

https://www.luogu.org/problemnew/show/P3959

注意到n非常小，考虑状压/搜索。

发现状压需要枚举起点，跑n次，一个问题是转移不可以以数字大小为阶段了，考虑用dfs的方式递推。

一开始的naive想法是，跑2^n次Floyd，处理出每种联通情况下到根的最少经过点数，然后由N-1状态开始倒着记忆化搜索，出了很多锅，细节也不少。

考虑正着做，即刷表，发现很好写！也不必跑Floyd了，用dis数组一边跑一边更新最短距离就行。

f[S]表示联通情况为s时的最小代价，转移时枚举一个集合内的点，由它向外枚举一个点转移。

#include<iostream>

#include<cstdio>

using namespace std;

inline int rd(){

    int ret=,f=;char c;

    while(c=getchar(),!isdigit(c))f=c=='-'?-:;

    while(isdigit(c))ret=ret*+c-'',c=getchar();

    return ret*f;

}

const int MAXN=;

const int INF=<<;

int n,m,N;

int a[MAXN][MAXN];

int f[<<MAXN],dis[<<MAXN];

void dp(int s){

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

        if(!(s&(<<(i-)))) continue;

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

            if(s&(<<(j-))) continue;

            if(a[i][j]==INF) continue;

            if(f[s|(<<(j-))]>f[s]+(dis[i]+)*a[i][j]){

                int sav=dis[j];

                dis[j]=dis[i]+;

                f[s|(<<(j-))]=f[s]+(dis[i]+)*a[i][j];

                dp(s|(<<(j-)));

                dis[j]--;

            }

        }

    }

}

int main(){

    n=rd();m=rd();N=<<n;

    int x,y,w;

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

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

            a[i][j]=INF;

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

        x=rd();y=rd();w=rd();

        a[y][x]=a[x][y]=min(a[x][y],w);

    }

    int ans=INF;

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

        for(int j=;j<N;j++) f[j]=INF;

        for(int j=;j<=n;j++) dis[j]=INF;

        f[]=;f[<<(i-)]=;dis[i]=;

        dp(<<(i-));

        ans=min(ans,f[N-]);

    }

    cout<<ans;

    return ;

}

巴特西

[LUOGU] 3959 宝藏

最新文章

热门文章