Bỏ qua

Tách đỉnh (Node Splitting)

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

结点有流量限制的最大流

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

我们考虑把有流量限制的结点转化成这样一种形式：由两个结点 \(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\) 的最小花费．

参考核心代码：

 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);
}
Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:Anguei, sshwy, Xeonacid, Ir1d, MonkeyOliver, hsfzLZH1
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply