题目链接

Luogu P3959

这一题有两种做法：状压dp和模拟退火

<h1>解题思路</h1>
看到这一道题目的时候，我的第一反应就是：裸的Prim啊！

但仔细思考了一下，发现事情没有那么简单：

长度和层数都对后面的结果有影响，所以不能贪心的求Prim，贪心会导致局部最优解，最终分数会很低。

然后看到了N很小，所以就用了一种伪·模拟退火来做这一道题。

思想就是我们选取一个随机数，给定被淘汰的状态一个“复活”的机会，来借此逃避局部最优解。

也就是伪·模拟退火。
<h1>代码</h1>

#include 
#include 
#include 
#include 
#include 
#include 
#include 

const int MAXN = 12 + 5;

int mapMAXN,depth[MAXN];

struct Edge{
    int u,v;
    bool operator < (const Edge other) const{ return depth[u]  mapu > depth[other.u]  mapother.u;
    }
};

int N,M;

int search(int x){
    memset(depth,0,sizeof(depth));
    bool vis[MAXN] = {false};
    std::priority_queue h;
    Edge past[1000 + 5];int p = 0;
    struct Edge e,e2;
    int cost = 0;
    depth[x] = 1;
    vis[x] = true;
    for(int i = 1;i <= N;i++){
        if(mapx != INT_MAX){
            e.u = x;e.v = i;
            h.push(e);
        }
    }
    for(int i = 1;i < N;i++){
        e = h.top();h.pop();
        while(!h.empty() && ((vis[e.v] || rand() % (N) < 1))){ //N越大，表示复活的机会越小。 if(!vis[e.v]) past[p++] = e; e = h.top();h.pop(); } vis[e.v] = true; depth[e.v] = depth[e.u] + 1; if(p-- > 0)
            for(;p >= 0;--p)
                h.push(past[p]);
        p = 0;
        for(int i = 1;i <= N;i++){
            if(mape.v != INT_MAX && !vis[i]){
                e2.u = e.v;e2.v = i;
                h.push(e2);
            }
        }
        cost += mape.u * depth[e.u];
    }
    return cost;
}

int main(){
    scanf("%d%d",&N,&M);
    for(int i = 1;i <= N;i++)
        for(int j = 1;j <= N;j++)
            mapi = INT_MAX;
    for(int a,b,c,i = 1;i <= M;i++){
        scanf("%d%d%d",&a,&b,&c);
        mapa = mapb = std::min(c,mapa);
    }
        srand(time(NULL));
    srand(rand()^rand()^20050117);
    int ans = INT_MAX;
    for(int j = 1;j < 1000;j++){
        for(int i = 1;i <= N;i++){
            ans = std::min(ans,search(i));
        }
    }
    printf("%dn",ans);
    return 0;
}

<h1>状压做法</h1>
看到 $n$ 这么小我们当然要考虑状压dp了。
设计状态 $f_{i,S}$ 表示当前宝藏屋打通状态为 $S$,已经打到了第 $i$ 层的最小代价。
显然转移枚举这一次打通哪一个并且和新打通的在同一层都有多少个就可以了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
//#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    #define ll long long
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],p1=buf+BUF_SIZE,pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='n'||ch=='r'||ch=='t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(ll &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    #undef ll
    #undef OUT_SIZE
    #undef BUF_SIZE
};
using namespace fastIO;
#define int LL
const int MAXN = 12 + 5;
const int MAXX = (1<<12)+5;
int mapMAXN;
int N,M;
int v[MAXX],pos[MAXX];
int log[MAXX],g[MAXX],state[MAXX];
int fMAXN;
#define lowbit(x) (x&-x)
signed main(){
    read(N);read(M);
    FOR(i,1,N) FOR(j,1,N) mapi = INT_MAX;
    FOR(i,1,M){
        int u,v,w;read(u);read(v);read(w);
        mapu = mapv = std::min(mapu,w);
    }
    int MAX = (1<<N)-1;
    CLR(f,0x3f);
    FOR(i,0,N) f1 = 0;
    FOR(i,0,N) log[1<<i]=i;
    FOR(i,1,N){
        FOR(j,0,MAX){
            int cnt = 0;
            FOR(k,1,N){
                if(!(j&(1<<(k-1)))){
                    cnt++;
                    v[cnt] = INT_MAX;
                    pos[cnt] = (1<<(k-1));
                    int t = j;
                    while(t){
                        int e = log[lowbit(t)]+1;//DEBUG(e);
                        if(mapk < INT_MAX) v[cnt] = std::min(v[cnt],mapk*i);
                        t -= lowbit(t);
                    }
                }
            }
            int size = (1<<cnt)-1;
            FOR(k,1,size){
                g[k] = g[k-lowbit(k)]+v[log[lowbit(k)]+1];
                state[k] = state[k-lowbit(k)] | pos[log[lowbit(k)]+1];
                fi+1] = std::min(fi+1],fi+g[k]);
            }
        }
    }
    int ans = INT_MAX;
    FOR(i,1,N) ans = std::min(ans,fi);
    printf("%lldn",ans);
    return 0;
}