【题解】LuoGu3959/noip2017：宝藏

原题传送门

状压dp

$dp[i][j][s]$表示当前在j节点，j到起点距离为i，从j开始挖的点的集合为s的最小代价
所以我们要先保证j不属于s，再枚举出一个属于s的集合s2，在s2里枚举出一个属于s2的点k，S1记为s2-{k},S2记为$s-s2$

状态转移方程：$dp[i][j][s]=min(dp[i+1][k][S1]+dp[i][j][S2]+w[j][k]\ast (i+1))$

最终枚举起点求得答案

Code：

#include <bits/stdc++.h>
#define maxn 21
#define maxm 10000
using namespace std;
const int inf = 0x3f3f3f3f;
int w[maxn][maxn], power[maxn], pos[maxm], dp[maxn][maxn][maxm], n, m;

inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

int main(){
    n = read(), m = read();
    memset(dp, 0x3f, sizeof(dp));
    memset(w, 0x3f, sizeof(w));
    for (int i = 1; i <= m; ++i){
        int x = read(), y = read(), z = read(); --x, --y;
        w[x][y] = w[y][x] = min(w[x][y], z);
    }
    power[0] = 1; 
    for (int i = 1; i <= n; ++i) power[i] = power[i - 1] << 1;
    for (int i = 0; i <= n; ++i) pos[power[i]] = i;
    for (int i = 0; i < n; ++i) dp[n - 1][i][0] = 0;
    for (int i = n - 2; i >= 0; --i)
        for (int j = 0; j < n; ++j){
            dp[i][j][0] = 0;
            for (int s = 1; s < power[n]; ++s)
                if ((s & power[j]) == 0)
                    for (int s1 = s; s1; s1 = (s1 - 1) & s)
                        if (dp[i][j][s & ~s1] < dp[i][j][s]){
                            int s2 = s1;
                            while (s2){
                                int x = s2 & -s2, k = pos[x];
                                if (w[j][k] < inf) dp[i][j][s] = min(dp[i][j][s], dp[i][j][s & ~s1] + dp[i + 1][k][s1 & ~x] + (i + 1) * w[j][k]);
                                s2 &= ~x;
                            }
                        }
        }
    int ans = inf; 
    for (int i = 0; i < n; ++i) ans = min(ans, dp[0][i][(power[n] - 1) & ~power[i]]);
    printf("%d\n", ans);
    return 0;
}

uses math;
var
    dp:array[0..20,0..20,0..10000] of longint;
    w:array[0..100,0..100] of longint;
    pow,p:array[0..10000] of longint;
    n,m,x,y,z,i,j,k,s1,s2,s3:longint;
    ans:int64;

begin
    readln(n,m);
    fillchar(w,sizeof(w),$7f);
    fillchar(dp,sizeof(dp),$7f);
    for i := 1 to m do
    begin
        readln(x,y,z);
        dec(x); dec(y);
        w[x][y] := min(w[x][y], z);
        w[y][x] := min(w[y][x], z);
    end;
    pow[0] := 1;
    for i := 1 to n do pow[i] := pow[i - 1] << 1;
    for i := 0 to n - 1 do p[pow[i]] := i; //p[2^i]=i，预处理
    for i := 0 to n - 1 do dp[n - 1][i][0] := 0;
    for i := n - 2 downto 0 do
        for j := 0 to n - 1 do
        begin
            dp[i][j][0] := 0;
            for s1 := 1 to pow[n] - 1 do
                if s1 and pow[j] = 0 then
                begin
                    s2 := s1;
                    while s2 > 0 do
                    begin
                        if dp[i][j][s1 and not s2] < dp[i][j][s1] then
                        begin
                            s3 := s2;
                            while s3 > 0 do
                            begin
                                x := s3 and -s3;
                                //x枚举s3包括的点
                                y := p[x];
                                if w[j][y] < 2000000000 then
                                    dp[i][j][s1] := min(dp[i][j][s1],
                                        (i + 1) * w[j][y] + dp[i + 1][y][s2 and not x] + dp[i][j][s1 and not s2]);
                                dec(s3, x);
                            end;
                        end;
                        s2 := (s2 - 1) and s1; 
                        //s2枚举s1的子集
                    end;
                end;
        end;
    ans := maxlongint;
    for i := 0 to n - 1 do ans := min(ans, dp[0][i][(pow[n] - 1) and not pow[i]]);
    writeln(ans);
end.