拆点

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

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

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

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

如果原图是这样：

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

分层图最短路¶

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

其中，表示的父亲节点，表示当前所走的边的边权。当时， = 。

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

「JLOI2011」飞行路线

题意：有一个个点条边的无向图，你可以选择条道路以零代价通行，求到的最小花费。

参考核心代码：

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);
}

Last update and/or translate time of this article，Check the history
Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
Contributor of this article Anguei, sshwy, Xeonacid, Ir1d, MonkeyOliver, hsfzLZH1
Translator of this article Visit the original article!
The article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

拆点

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

分层图最短路¶

Comments