斯坦納樹

網(wǎng)上關(guān)于這玩意兒的資料不是很多

度娘的定義

斯坦納樹問題是組合優(yōu)化問題，與最小生成樹相似，是最短網(wǎng)絡(luò)的一種。 最小生成樹是在給定的點集和邊中尋求最短網(wǎng)絡(luò)使所有點連通。 而最小斯坦納樹允許在給定點外增加額外的點，使生成的最短網(wǎng)絡(luò)開銷最小。

我個人認(rèn)為這玩意兒應(yīng)該是某一類沒有多項式解法的最小生成樹問題，然后可以用狀壓DP求解

直接從一道題目入手

?

?

[WC2008]游覽計劃

鏈接

這應(yīng)該算是斯坦納樹的板子題了

我們令$f[i][sta]$表示$i$號節(jié)點，與其他節(jié)點的聯(lián)通性為$sta$時的最小代價，這里的$sta$是一個二進(jìn)制數(shù)，在它二進(jìn)制下的每一位中，$0$表示不連通，$1$表示聯(lián)通

那么轉(zhuǎn)移的時候會有兩種情況

• 由子集轉(zhuǎn)移而來

方程為$$f[i][sta] = \min_{s \in sta}\{f[i][s] + f[i][\complement_ssta] - val[i]\}$$

后面的減是防止加重

這里在枚舉子集的時候有一個技巧

for(int s = sta; s; s = (s - 1) & sta)

這樣可以枚舉出sta的所有子集

• 由不含該節(jié)點的狀態(tài)轉(zhuǎn)移而來

?轉(zhuǎn)移方程為

其中$i$為新加入的節(jié)點

$$f[i][j] = \min\{f[k][j] + val[i]\}$$

大家看到這個方程有沒有一種很熟悉的感覺？

是不是很像三角形不等式？

因此，我們可以用SPFA進(jìn)行這種轉(zhuǎn)移

?

完整代碼

// luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<cstdio> #include<queue> #include<cstring> using namespace std; const int limit = 1050; const int INF = 1e9; inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}return x * f; } #define MP(i,j) make_pair(i,j) #define se second #define fi first #define Pair pair<int,int> int N, M, tot = 0; int a[12][12], f[12][12][limit]; int xx[5] = {-1, +1, 0, 0}; int yy[5] = {0, 0, -1, +1}; int vis[12][12]; struct PRE {int x, y, S; }Pre[12][12][limit]; queue<Pair>q; void SPFA(int cur) {while(q.size() != 0) {Pair p = q.front();q.pop();vis[p.fi][p.se] = 0;for(int i = 0; i <4; i++) {int wx = p.fi + xx[i], wy = p.se + yy[i];if(wx < 1 || wx > N || wy < 1 || wy > M) continue;if(f[wx][wy][cur] > f[p.fi][p.se][cur] + a[wx][wy]) {f[wx][wy][cur] = f[p.fi][p.se][cur] + a[wx][wy];Pre[wx][wy][cur] = (PRE){p.fi, p.se, cur};if(!vis[wx][wy])vis[wx][wy] = 1, q.push(MP(wx,wy));}}} } void dfs(int x, int y, int now) {vis[x][y] = 1;PRE tmp = Pre[x][y][now];if(tmp.x == 0 && tmp.y == 0) return;dfs(tmp.x, tmp.y, tmp.S);if(tmp.x == x && tmp.y == y) dfs(tmp.x, tmp.y, now - tmp.S); } int main() {//freopen("a.in", "r", stdin);N = read(); M = read();memset(f, 0x3f, sizeof(f));for(int i = 1; i <= N; i++)for(int j = 1; j <= M; j++) {a[i][j] = read();if(a[i][j] == 0)f[i][j][1 << tot] = 0, tot++;}int limit = (1 << tot) - 1;for(int sta = 0; sta <= limit; sta++) {for(int i = 1; i<= N; i++)for(int j = 1; j <= M;j++) {for(int s = sta; s; s = (s - 1) & sta) {if(f[i][j][s] + f[i][j][sta - s] - a[i][j] < f[i][j][sta])f[i][j][sta] = f[i][j][s] + f[i][j][sta - s] - a[i][j],Pre[i][j][sta] = (PRE){i,j,s};}if(f[i][j][sta] < INF) q.push(MP(i,j)), vis[i][j] = 1;}SPFA(sta);}int ansx, ansy, flag = 0;for(int i = 1; i <= N && !flag; i++)for(int j = 1; j <= M; j++)if(!a[i][j]) {ansx = i, ansy = j; flag = 1; break;}printf("%d\n",f[ansx][ansy][limit]); memset(vis, 0, sizeof(vis));dfs(ansx, ansy, limit);for(int i = 1; i <= N; i++, puts("")) {for(int j = 1; j <= M; j++) {if(a[i][j] == 0) putchar('x');else if(vis[i][j]) putchar('o');else putchar('_'); } } return 0; }

?

?

?

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的斯坦纳树小结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。