P3959

· · 个人记录

[NOIP2017 提高组] 宝藏

开始想了个思路，并不知道何处假了。

定义 f(i,j,k) 表示状态为 i，其中一点 j 的深度为 k 的最小代价。

然后拓展，发现更新，一并更新前驱的状态。

我认为它可以构成链，并且链套链组成树（因为状压的不有序）。

使用的解法看起来非常正确，但不知道证明。

定义 f(i,j,k) 表示状态为 i，有一点 j，其深度为 k（但是起点不一定包含在集合中）。

然后转移的话需要枚举子集：

f(S,i,k)=\min\{f(S1,i,k)+f(S2,j,k+1)+edge(i,j)k\}

然后就没了。

时间复杂度 O(n^33^n)。

后来我又思考了一下，其实这里直接按层数转移也是正确的，因为不同层数带来的转移是叠加的，不如说比我一开始想的做法更容易想出正确性。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll int
using namespace std;

const ll inf=0x3f3f3f3f,N=12,I=5e4;

ll n,m,u,v,w,ans;

ll edge[N+5][N+5],f[I+5][N+5][N+5];

ll dp(ll S,ll p,ll k) {
    if(f[S][p][k]!=-1) return f[S][p][k];
    if(S==(1<<(p-1))) return f[S][p][k]=0;
    f[S][p][k]=inf;
    for(ll S1=S;S1;S1=(S1-1)&S) {
        if(!(S1&(1<<(p-1)))) continue;
        for(ll q=1;q<=n;q++) {
            if(!(S&(1<<(q-1)))) continue;
            if(!edge[p][q]) continue;
            ll S2=S^S1;
            f[S][p][k]=min(f[S][p][k],
            dp(S1,p,k)+dp(S2,q,k+1)+edge[p][q]*k);
        }
    }
    return f[S][p][k];
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=m;i++) {
        u=read();v=read();w=read();
        if(edge[u][v]==0||edge[u][v]>w) {
            edge[u][v]=edge[v][u]=w;
        }
    }
    memset(f,-1,sizeof(f));
    ans=inf;
    for(ll i=1;i<=n;i++) {
        ans=min(ans,dp((1<<n)-1,i,1));
    }
    write(ans);

    return 0;
}