拆點

拆點是一種圖論建模思想，常用於網絡流，用來處理 點權或者點的流量限制 的問題，也常用於 分層圖。

結點有流量限制的最大流

如果把結點轉化成邊，那麼這個問題就可以套板子解決了。

我們考慮把有流量限制的結點轉化成這樣一種形式：由兩個結點 \(u,v\) 和一條邊 \(\left\langle u,v \right\rangle\) 組成的部分。其中，結點 \(u\) 承接所有從原圖上其他點的出發到原圖上該點的邊，結點 \(v\) 引出所有從原圖上該點出發到達原圖上其他點的邊。邊 \(\left\langle u,v \right\rangle\) 的流量限制為原圖該點的流量限制，再套板子就可以解決本題。這就是拆點的基本思想。

如果原圖是這樣：

拆點之後的圖是這個樣子：

分層圖最短路

分層圖最短路，如：有 \(k\) 次零代價通過一條路徑，求總的最小花費。對於這種題目，我們可以採用 DP 相關的思想，設 \(\text{dis}_{i, j}\) 表示當前從起點 \(i\) 號結點，使用了 \(j\) 次免費通行權限後的最短路徑。顯然，\(\text{dis}\) 數組可以這麼轉移：

\(\text{dis}_{i, j} = \min\{\min\{\text{dis}_{from, j - 1}\}, \min\{\text{dis}_{from,j} + w\}\}\)

其中，\(from\) 表示 \(i\) 的父親節點，\(w\) 表示當前所走的邊的邊權。當 \(j - 1 \geq k\) 時，\(\text{dis}_{from, j}\)=\(\infty\)。

事實上，這個 DP 就相當於把每個結點拆分成了 \(k+1\) 個結點，每個新結點代表使用不同多次免費通行後到達的原圖結點。換句話説，就是每個結點 \(u_i\) 表示使用 \(i\) 次免費通行權限後到達 \(u\) 結點。

「JLOI2011」飛行路線

題意：有一個 \(n\) 個點 \(m\) 條邊的無向圖，你可以選擇 \(k\) 條道路以零代價通行，求 \(s\) 到 \(t\) 的最小花費。

參考核心代碼：

struct State {    // 優先隊列的結點結構體
  int v, w, cnt;  // cnt 表示已經使用多少次免費通行權限

  State() {}

  State(int v, int w, int cnt) : v(v), w(w), cnt(cnt) {}

  bool operator<(const State &rhs) const { return w > rhs.w; }
};

void dijkstra() {
  memset(dis, 0x3f, sizeof dis);
  dis[s][0] = 0;
  pq.push(State(s, 0, 0));  // 到起點不需要使用免費通行權，距離為零
  while (!pq.empty()) {
    const State top = pq.top();
    pq.pop();
    int u = top.v, nowCnt = top.cnt;
    if (done[u][nowCnt]) continue;
    done[u][nowCnt] = true;
    for (int i = head[u]; i; i = edge[i].next) {
      int v = edge[i].v, w = edge[i].w;
      if (nowCnt < k && dis[v][nowCnt + 1] > dis[u][nowCnt]) {  // 可以免費通行
        dis[v][nowCnt + 1] = dis[u][nowCnt];
        pq.push(State(v, dis[v][nowCnt + 1], nowCnt + 1));
      }
      if (dis[v][nowCnt] > dis[u][nowCnt] + w) {  // 不可以免費通行
        dis[v][nowCnt] = dis[u][nowCnt] + w;
        pq.push(State(v, dis[v][nowCnt], nowCnt));
      }
    }
  }
}

int main() {
  n = read(), m = read(), k = read();
  // 筆者習慣從 1 到 n 編號，而這道題是從 0 到 n - 1，所以要處理一下
  s = read() + 1, t = read() + 1;
  while (m--) {
    int u = read() + 1, v = read() + 1, w = read();
    add(u, v, w), add(v, u, w);  // 這道題是雙向邊
  }
  dijkstra();
  int ans = std::numeric_limits<int>::max();  // ans 取 int 最大值為初值
  for (int i = 0; i <= k; ++i)
    ans = std::min(ans, dis[t][i]);  // 對到達終點的所有情況取最優值
  println(ans);
}

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Anguei, sshwy, Xeonacid, Ir1d, MonkeyOliver, hsfzLZH1
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用