給定\(n\)個點，\(m\)條邊的帶權無向圖

選出一些邊，使得\(4\)對點之間可達，詢問權值最小為多少

\(n \leqslant 30, m \leqslant 1000\)

---

首先看數(shù)據(jù)范圍，\(4\)對點，也就是\(8\)個點，很小

上斯坦納樹（局部最小生成樹）

然而好像題目并不是斯坦納樹，可能是一些樹拼到一起

那么就再做一個狀壓\(dp\)即可

復雜度\(O(3^8 * n + 2^8 * nm + 2^{12} * n)\)

---

#include <map> #include <queue> #include <cstdio> #include <cstring> #include <iostream> using namespace std;const int sid = 55; const int eid = (1 << 9) - 1; inline void cmin(int &a, int b) { if(a > b) a = b; }int n, m, nc; int U[sid], V[sid], cl[sid], ip[sid]; int f[sid][eid], E[sid][sid]; string s[55], sa, sb; map <string, int> id;int inq[sid]; queue <int> q; void spfa(int S) {memset(inq, 0, sizeof(inq));for(int i = 1; i <= n; i ++) q.push(i);while(!q.empty()) {int id = q.front(); q.pop(); inq[id] = 0;for(int j = 1; j <= n; j ++)if(f[j][S] > f[id][S] + E[id][j]) {f[j][S] = f[id][S] + E[id][j];if(!inq[j]) q.push(j), inq[j] = 1;}} }void wish1() {memset(f, 56, sizeof(f));for(int i = 1; i <= n; i ++)if(cl[i]) {nc ++;ip[i] = nc;f[i][(1 << nc - 1)] = 0;}for(int S = 0; S <= (1 << nc) - 1; S ++) {for(int i = 1; i <= n; i ++)for(int T = S; T; T = (T - 1) & S)cmin(f[i][S], f[i][T] + f[i][S ^ T]);spfa(S);} }int g[eid]; void wish2() {memset(g, 56, sizeof(g)); g[0] = 0;for(int s = 0; s <= (1 << 4) - 1; s ++)for(int i = 1; i <= n; i ++)for(int S = 0; S <= (1 << nc) - 1; S ++) {int T = 0;for(int k = 1; k <= 4; k ++)if((S & (1 << ip[U[k]] - 1)) && (S & (1 << ip[V[k]] - 1)))T |= (1 << k - 1);cmin(g[s | T], g[s] + f[i][S]);}printf("%d\n", g[(1 << 4) - 1]); }int main() {freopen("bzoj1402.in", "r", stdin);freopen("bzoj1402.out", "w", stdout);cin >> n >> m;for(int i = 1; i <= n; i ++) {cin >> s[i];id[s[i]] = i;}memset(E, 56, sizeof(E));for(int i = 1; i <= m; i ++) {int u, v, w;cin >> sa >> sb >> w;u = id[sa]; v = id[sb];cmin(E[u][v], w); E[v][u] = E[u][v];}for(int i = 1; i <= 4; i ++) {int u, v;cin >> sa >> sb;u = id[sa]; v = id[sb];U[i] = u; V[i] = v;cl[u] = cl[v] = 1;}wish1(); wish2();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/reverymoon/p/10076783.html

總結(jié)

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

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