跳转至

# 拆点

拆点是一种图论建模思想，常用于 网络流，用来处理 点权或者点的流量限制 的问题，也常用于 分层图．

## 结点有流量限制的最大流

如果把结点转化成边，那么这个问题就可以套板子解决了．

我们考虑把有流量限制的结点转化成这样一种形式：由两个结点 𝑢,𝑣 u,v 和一条边 ⟨𝑢,𝑣⟩⟨u,v⟩ 组成的部分．其中，结点 𝑢 u 承接所有从原图上其他点的出发到原图上该点的边，结点 𝑣 v 引出所有从原图上该点出发到达原图上其他点的边．边 ⟨𝑢,𝑣⟩⟨u,v⟩ 的流量限制为原图该点的流量限制，再套板子就可以解决本题．这就是拆点的基本思想．

如果原图是这样：

拆点之后的图是这个样子：

## 分层图最短路

分层图最短路，如：有 𝑘 k 次零代价通过一条路径，求总的最小花费．对于这种题目，我们可以采用 DP 相关的思想，设 d i s 𝑖,𝑗 dis i,j 表示当前从起点 𝑖 i 号结点，使用了 𝑗 j 次免费通行权限后的最短路径．显然，d i s dis 数组可以这么转移：

d i s 𝑖,𝑗 =m i n{m i n{d i s 𝑓 𝑟 𝑜 𝑚,𝑗−1},m i n{d i s 𝑓 𝑟 𝑜 𝑚,𝑗 +𝑤}}dis i,j=min{min{dis f r o m,j−1},min{dis f r o m,j+w}}

其中，𝑓 𝑟 𝑜 𝑚 f r o m 表示 𝑖 i 的父亲节点，𝑤 w 表示当前所走的边的边权．当 𝑗 −1 ≥𝑘 j−1≥k 时，d i s 𝑓 𝑟 𝑜 𝑚,𝑗 dis f r o m,j=∞∞．

事实上，这个 DP 就相当于把每个结点拆分成了 𝑘 +1 k+1 个结点，每个新结点代表使用不同多次免费通行后到达的原图结点．换句话说，就是每个结点 𝑢 𝑖 u i 表示使用 𝑖 i 次免费通行权限后到达 𝑢 u 结点．

「JLOI2011」飞行路线

题意：有一个 𝑛 n 个点 𝑚 m 条边的无向图，你可以选择 𝑘 k 条道路以零代价通行，求 𝑠 s 到 𝑡 t 的最小花费．

参考核心代码：

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    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);
    }

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, mcendu, ouuan, Anguei, Chrogeek, Enter-tainer, Henry-ZHR, hsfzLZH1, ksyx, MonkeyOliver, sshwy, Tiphereth-A, Xeonacid
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用