洛谷P4294 [WC2008]游览计划（斯坦纳树）

题目链接

题意

给一个网格图，每点存在点权，求一个连接某 $k(k<=10)$ 个点的最小生成树。 权值为 $0$ 表示需要连接的点

思路

首先排除求任意两点之间求最短路，然后最小生成树做法，因为会有重复经过的点。 可以使用插头dp 这里写了状压DP+bfs求斯坦纳树做法。 考虑状态 $DP[i][j][s]=以ij为根连通状态至少为s的最小值$ 考虑转移 $DP[i][j][s]=min(DP[i][j][s],DP[i][j][t]+DP[i][j][s-t]-a[i][j])，t为s子状态$ $DP[ni][nj][s]=min(DP[ni][nj][s],DP[i][j][s]+a[ni][nj])，ni、nj表示与i、j相邻点$，这里使用bfs转移（spfa）

路径输出：记录每个状态前驱瞎搞下，某状态可能有两个前驱，但肯定，两个子状态之和等于当前状态。

据说状压枚举子集复杂度是 $O(3^k)$ 那么斯坦纳树算法复杂度应该是 $O(3^k\ast n\ast m)$ = $3^{(需要连接点集大小)}\ast 点数+2^{(需要连接点集大小)}\ast (点数+边数)$ 以上是我瞎扯的，实际应该比我这小

代码

斯坦纳树 241ms 吸氧后 99ms

#include <bits/stdc++.h> using namespace std; #define ll long long #define _p pair<int,int> #define x first #define y second struct Node { int x, y, s; }pre[15][15][1<<10]; int n, m, k; int bit[20], a[15][15], dp[15][15][1<<10], ex, ey, vis[15][15], mov[4][2] = {0,1,1,0,0,-1,-1,0}; queue<_p> q; void spfa(int sta) { while(!q.empty()) { int x = q.front().x, y = q.front().y; q.pop(); for(int i = 0; i < 4; ++i) { int nx = mov[i][0]+x, ny = mov[i][1]+y; if(nx < 1 || nx > n || ny < 1 || ny > m) continue; if(dp[nx][ny][sta] > dp[x][y][sta]+a[nx][ny]) { dp[nx][ny][sta] = dp[x][y][sta]+a[nx][ny]; pre[nx][ny][sta] = {x,y,sta}; if(!vis[nx][ny]) vis[nx][ny] = 1, q.push({nx,ny}); } } vis[x][y] = 0; } } void dfs(int x, int y, int sta) { if(x == 0 || pre[x][y][sta].s == 0) return; vis[x][y] = 1; Node tmp = pre[x][y][sta]; if(tmp.x == x && tmp.y == y) dfs(x,y,sta^tmp.s); dfs(tmp.x,tmp.y,tmp.s); } int main() { bit[0] = 1; for(int i = 1; i <= 10; ++i) bit[i] = bit[i-1]<<1; while(~scanf("%d%d",&n,&m)) { k = 0; memset(pre,0,sizeof(pre)); memset(dp,0x3f,sizeof(dp)); memset(vis,0,sizeof(vis)); for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { scanf("%d",&a[i][j]); if(a[i][j] == 0) ex = i, ey = j, dp[i][j][1<<k] = 0, ++k; } } for(int now = 1; now < (1<<k); ++now) { for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { for(int k = now&(now-1); k; k = now&(k-1)) { if(dp[i][j][now] > dp[i][j][k]+dp[i][j][now^k]-a[i][j]) { dp[i][j][now] = dp[i][j][k]+dp[i][j][now^k]-a[i][j]; pre[i][j][now] = {i,j,k}; } } if(dp[i][j][now] != 0x3f3f3f3f) q.push({i,j}), vis[i][j] = 1; } } spfa(now); } printf("%d\n",dp[ex][ey][(1<<k)-1]); dfs(ex,ey,(1<<k)-1); for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { if(!a[i][j]) printf("x"); else if(vis[i][j]) printf("o"); else printf("_"); } printf("\n"); } } return 0; }