题解
真的想不到这题状压的做法。。。听说还有跑的飞快的模拟退火，要是现场做绝对滚粗QAQ。
不考虑深度，先预处理出 $pt_{i, S}$ 表示让一个不属于 集合 $S$ 的 点$i$ 与点集 $S$ 联通的最小代价， 也就是从 $i$ 到 $ j, j in S$的最小距离。
接着处理$ss_{S, T}$, $Ssubset T$, 表示从集合$S$拓展到$T$所需要的最小代价。
最后求出$f_{i, j}$ 表示当前已到 深度$i$, 已经扩展到集合$S$时耗费的最小代价. 答案就是$ min(f_{i, U })$ $ i in [0, n - 1]$
是可以求出所有的挖掘方案中的最小代价， 是个正确算法（吧,应该
代码
1 #include<cstring> 2 #include<algorithm> 3 #include<cstdio> 4 #define rd read() 5 #define rep(i,a,b) for( int i = (a); i <= (b); ++i ) 6 #define per(i,a,b) for( int i = (a); i >= (b); --i ) 7 using namespace std; 8 9 const int N = 15; 10 const int M = 1 << 13; 11 const int inf = 1061109567; 12 13 int pt[N][M], ss[M][M], f[N][M], mp[N][N], n, m; 14 15 inline int read() { 16 int X = 0, p = 1; char c = getchar(); 17 for(; c > '9' || c < '0'; c = getchar() ) if( c == '-' ) p = -1; 18 for(; c >= '0' && c <= '9'; c = getchar() ) X = X * 10 + c - '0'; 19 return X * p; 20 } 21 22 inline void cmin( int &a, int b ) { 23 if( a > b ) a = b; 24 } 25 26 int main() 27 { 28 n = rd; m = rd; 29 memset(pt, 63, sizeof(pt)); 30 memset(f, 63, sizeof(f)); 31 memset(mp, 63, sizeof(mp)); 32 rep( i, 1, m ) { 33 int u = rd - 1, v = rd - 1, w = rd;//我从0开始存点 34 cmin( mp[u][v], w ); 35 cmin( mp[v][u], w ); 36 } 37 //求出点连到集合的最小代价 38 rep( S, 0, (1 << n) - 1 ) 39 rep( i, 0, n - 1 ) if((S >> i) & 1) 40 rep( j, 0, n - 1 ) if(!((S >> j) & 1)) 41 cmin( pt[j][S], mp[j][i] ); 42 //求出集合扩展的最小代价 43 rep( S, 0, (1 << n) - 1 ) 44 for( int j = S & (S - 1); j; j = S & (j - 1) ) {//j为S 的子集，神奇的枚举子集方法 45 int left = S ^ j; 46 rep( i, 0, n - 1 ) if((left >> i) & 1) 47 ss[j][S] = min( ss[j][S] + pt[i][j], inf ); 48 } 49 50 rep( i, 0, n - 1 ) f[0][1 << i] = 0; 51 rep( i, 1, n - 1 ) 52 rep( S, 0, (1 << n) - 1 ) 53 for( int j = S & (S - 1); j; j = S & (j - 1) ) { 54 int tmp; 55 if( ss[j][S] != inf ) tmp = ss[j][S] * i;//集合能够扩展 56 else tmp = inf; 57 if( f[i - 1][j] != inf ) cmin( f[i][S], f[i - 1][j] + tmp );//上一步的状态可行 58 } 59 int ans = inf; 60 rep( i, 0, n - 1 ) cmin( ans, f[i][ (1 << n) - 1] );//求出最小值 61 printf("%d ", ans); 62 }