20200912 專題：斯坦納樹

總覽：

給定一個包含 n n n 個結點和 m m m 條帶權邊的無向連通圖 G = ( V , E ) G=(V,E) G=(V,E)

再給定包含 k k k 個結點的點集 S S S，選出 G G G 的子圖 G ′ = ( V ′ , E ′ ) G'=(V',E') G′=(V′,E′)，使得：

S ⊆ V ′ S\subseteq V' S⊆V′
G ′ G' G′ 為連通圖
E ′ E' E′ 中所有邊的權值和最小。

你隻需要求出 E ′ E' E′，中所有邊的權值和

這個問題可以用狀壓 DP 來解決

首先容易發現一個結論：答案的子圖一定是樹

證明：如果答案存在環，則删去環上任意一條邊，代價變小

于是我們為這棵樹欽定一個樹根，設 f i , S f_{i,S} fi,S 表示以 i i i 為根的一棵樹，包含集合 S S S 中所有點的最小代價， S S S 為若幹特殊點的點集

考慮如何不重不漏地轉移

一棵以 i i i 為根的樹有兩種情況，第一種是 i i i 的度數為 1 1 1，另一種是 i i i 的度數大于 1 1 1

對于 i i i 的度數大于 1 1 1 的情況，可以劃分成幾個子樹考慮，即：

f i , S = f i , T + f i , S − T ( T ∈ S ) f_{i,S}=f_{i,T}+f_{i,S-T}(T\in S) fi,S=fi,T+fi,S−T(T∈S)

可以直接枚舉子集進行轉移
對于 i i i 的度數為 1 1 1 的情況，可以從與 i i i 相鄰的點 j j j 轉移過來

f i , S = f j , S + w j , i f_{i,S}=f_{j,S}+w_{j,i} fi,S=fj,S+wj,i

這個類似最短路的轉移，可以 d j k djk djk

T1 P6192 【模闆】最小斯坦納樹

思路：

闆子題

代碼：

#include <bits/stdc++.h>
using namespace std;

#define re register
#define LL long long
typedef unsigned int uint;
typedef unsigned long long ull;
#define pb push_back
#define mp make_pair

namespace IO {
char _buf[1 << 21], *_p1 = _buf, *_p2 = _buf;
#define ch()                                                                 \
  (_p1 == _p2 &&                                                             \
           (_p2 = (_p1 = _buf) + fread(_buf, 1, 1 << 21, stdin), _p1 == _p2) \
       ? EOF                                                                 \
       : *_p1++)
inline int in() {
  int s = 0, f = 1;
  char x = ch();
  for (; x < '0' || x > '9'; x = ch())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = ch()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}
char buf[1 << 21];
int p1 = -1;
inline void flush() {
  fwrite(buf, 1, p1 + 1, stdout);
  p1 = -1;
}
inline void pc(char x) {
  if (p1 == (1 << 21) - 1) flush();
  buf[++p1] = x;
}
inline void out(re int x) {
  char k[30];
  int pos = 0;
  if (!x) {
    pc('0');
    return;
  }
  if (x < 0) {
    pc('-');
    x = -x;
  }
  while (x) {
    k[++pos] = (x % 10) | 48;
    x /= 10;
  }
  for (re int i = pos; i; i--) pc(k[i]);
  return;
}
}  // namespace IO
using namespace IO;

const int INF = 1e9;
int n, m, K;
int head[105], tot_road;
struct Road {
  int nex, to, w;
} road[1005];
inline void edge(re int x, int y, int w) {
  road[++tot_road] = {head[x], y, w}, head[x] = tot_road;
}
int p[105], f[105][2005];

int ex[105];
priority_queue<pair<int, int> > q;

inline void djk(int S) {
  for (re int i = 1; i <= n; ++i) {
    ex[i] = 0;
    if (f[i][S] != INF) q.push(mp(-f[i][S], i));
  }
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    if (ex[x]) continue;
    ex[x] = 1;
    for (re int y = head[x]; y; y = road[y].nex) {
      int z = road[y].to, w = road[y].w;
      if (f[z][S] > f[x][S] + w) {
        f[z][S] = f[x][S] + w;
        q.push(mp(-f[z][S], z));
      }
    }
  }
  return;
}

signed main() {
  n = in(), m = in(), K = in();
  for (re int i = 1; i <= m; ++i) {
    int u = in(), v = in(), w = in();
    edge(u, v, w), edge(v, u, w);
  }
  for (re int i = 1; i <= n; ++i)
    for (re int j = 0; j < (1 << K); ++j) f[i][j] = INF;
  for (re int i = 1; i <= K; ++i) {
    p[i] = in();
    f[p[i]][(1 << (i - 1))] = 0;
  }
  for (re int s = 1; s < (1 << K); s++) {
    for (re int i = 1; i <= n; ++i)
      for (re int j = s & (s - 1); j; j = s & (j - 1))
        f[i][s] = min(f[i][s], f[i][j] + f[i][s ^ j]);
    djk(s);
  }
  out(f[p[1]][(1 << K) - 1]), pc('\n');
  flush();
  return 0;
}

T2 P3264 [JLOI2015]管道連接配接

思路：

因為要使使得任意相同頻道的情報站之間都建立通道連接配接，是以跑完斯坦納樹後還要 d p dp dp

令 g S g_S gS 為包含點集 S S S 的最小代價，一個頻道中的點要麼都在 S S S 中，要麼都不在

考慮 d p dp dp 方程

g S = g T + g S − T ( T ∈ S ) g_S=g_T+g_{S-T}(T\in S) gS=gT+gS−T(T∈S)

代碼：

#include <bits/stdc++.h>
using namespace std;

#define re register
#define LL long long
typedef unsigned int uint;
typedef unsigned long long ull;
#define pb push_back
#define mp make_pair

namespace IO {
char _buf[1 << 21], *_p1 = _buf, *_p2 = _buf;
#define ch()                                                                 \
  (_p1 == _p2 &&                                                             \
           (_p2 = (_p1 = _buf) + fread(_buf, 1, 1 << 21, stdin), _p1 == _p2) \
       ? EOF                                                                 \
       : *_p1++)
inline int in() {
  int s = 0, f = 1;
  char x = ch();
  for (; x < '0' || x > '9'; x = ch())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = ch()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}
char buf_[1 << 21];
int p1_ = -1;
inline void flush() {
  fwrite(buf_, 1, p1_ + 1, stdout);
  p1_ = -1;
}
inline void pc(char x) {
  if (p1_ == (1 << 21) - 1) flush();
  buf_[++p1_] = x;
}
inline void out(int x) {
  char k[30];
  int pos = 0;
  if (!x) {
    pc('0');
    return;
  }
  if (x < 0) {
    pc('-');
    x = -x;
  }
  while (x) {
    k[++pos] = (x % 10) | 48;
    x /= 10;
  }
  for (int i = pos; i; i--) pc(k[i]);
  return;
}
}  // namespace IO
using namespace IO;

const int A = 3e3 + 5;
const int INF = 1e9;
int n, m, K;
int be[A], p[A], sum[A];
int head[A], tot_road;
struct Road {
  int nex, to, w;
} road[2 * A];
inline void edge(int x, int y, int w) {
  road[++tot_road] = {head[x], y, w}, head[x] = tot_road;
}
int f[A][A], g[A];
int cn[A];

int ex[A];
priority_queue<pair<int, int> > q;

inline void djk(int S) {
  for (int i = 1; i <= n; i++) {
    if (f[i][S] != INF) q.push(mp(-f[i][S], i));
    ex[i] = 0;
  }
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    if (ex[x]) continue;
    ex[x] = 1;
    for (int y = head[x]; y; y = road[y].nex) {
      int z = road[y].to, w = road[y].w;
      if (f[z][S] > f[x][S] + w) {
        f[z][S] = f[x][S] + w;
        q.push(mp(-f[z][S], z));
      }
    }
  }
  return;
}

int num[A];

inline int check(int x) {
  for (int i = 1; i <= K; i++) num[i] = 0;
  for (int i = 1; x; i++, x >>= 1)
    if (x & 1) num[be[i]]++;
  int pos = 0;
  for (int i = 1; i <= K; i++)
    if (num[i] && num[i] != sum[i]) return 0;
  return 1;
}

signed main() {
  n = in(), m = in(), K = in();
  for (int i = 1; i <= m; i++) {
    int u = in(), v = in(), w = in();
    edge(u, v, w), edge(v, u, w);
  }
  for (int i = 1; i <= K; i++) {
    be[i] = in(), p[i] = in();
    sum[be[i]]++;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < (1 << K); j++) f[i][j] = INF;
  for (int i = 1; i <= K; i++) f[p[i]][1 << (i - 1)] = 0;
  for (int s = 1; s < (1 << K); s++) {
    for (int i = 1; i <= n; i++) {
      for (int j = s & (s - 1); j; j = s & (j - 1))
        f[i][s] = min(f[i][s], f[i][j] + f[i][s ^ j]);
    }
    djk(s);
  }
  for (int i = 0; i < (1 << K); i++) cn[i] = check(i);
  for (int i = 0; i < (1 << K); i++) g[i] = INF;
  for (int i = 0; i < (1 << K); i++)
    if (cn[i])
      for (int j = 1; j <= n; j++) g[i] = min(g[i], f[j][i]);
  for (int i = 0; i < (1 << K); i++)
    if (cn[i])
      for (int j = i & (i - 1); j; j = i & (j - 1))
        if (cn[j] && cn[i ^ j]) g[i] = min(g[i], g[j] + g[i ^ j]);
  out(g[(1 << K) - 1]), pc('\n');
  flush();
  return 0;
}

20200912 專題：斯坦納樹

總覽：

T1 P6192 【模闆】最小斯坦納樹

T2 P3264 [JLOI2015]管道連接配接

繼續閱讀

Android 進階繪圖（轉載自eoe）

iPhone5搭載iOS6：App應用與Siri攻略

javascript的encodeURIComponent

20200903 專題：值域分塊

Java中方法重寫和重載的差別

細說PHP：人人都能玩轉PHP和MySQL Web開發

Visual Studio程式員箴言

中國互動設計體驗日 CHINA INTERACTION DESIGN EXPERIENCE DAY 2012

郭利臣：黃金級綠色資料中心是怎麼煉成的？

WPF 中的window 窗體

氪周刊：關注網際網路創業

《大資料，小時代，向移動網際網路遷徙-2012上半年移動網際網路資料分享》_DCCI

Linux運維趨勢：阿裡運維監控那些事兒

Windows環境下32位彙編語言程式設計

20200804 專題：仙人掌（圓方樹）

reflect metadata & dependency injection