Skip to content

Node Splitting

Node splitting is a graph modeling technique commonly used in network flow to handle problems with node capacities or flow restrictions, and is also frequently applied in layered graphs.

Maximum Flow with Node Capacity Constraints

If we transform nodes into edges, this problem can be solved using standard templates.

We consider converting a node with capacity constraints into the following form: a component consisting of two nodes \(u,v\) and an edge \(\left\langle u,v \right\rangle\). Here, node \(u\) receives all edges from other nodes in the original graph that point to this node, and node \(v\) emits all edges from this node to other nodes in the original graph. The capacity of edge \(\left\langle u,v \right\rangle\) is set to the original node's capacity constraint. Then, applying the standard template solves the problem. This is the basic idea of node splitting.

If the original graph looks like this:

After splitting, the graph becomes:

Shortest Path in Layered Graphs

Shortest path in layered graphs, for example: given \(k\) opportunities to traverse a path at zero cost, find the minimum total cost. For such problems, we can adopt DP-related ideas. Let \(\text{dis}_{i, j}\) denote the shortest path from the starting point to node \(i\), having used \(j\) free passes. Clearly, the \(\text{dis}\) array can be updated as follows:

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

Here, \(from\) represents the parent node of \(i\), and \(w\) is the weight of the current edge. When \(j - 1 \geq k\), \(\text{dis}_{from, j} = \infty\).

In fact, this DP is equivalent to splitting each node into \(k+1\) new nodes, where each new node represents reaching the original node after using a certain number of free passes. In other words, each node \(u_i\) represents reaching node \(u\) after using \(i\) free passes.

「JLOI2011」Flight Route

Problem: Given an undirected graph with \(n\) nodes and \(m\) edges, you can choose \(k\) edges to traverse at zero cost. Find the minimum cost from \(s\) to \(t\).

Reference core code:

 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 {    // Struct for priority queue nodes
  int v, w, cnt;  // cnt indicates how many free passes have been used

  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));  // No free pass used to reach the start, distance zero
  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]) {  // Can use a free pass
        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) {  // Cannot use a free pass
        dis[v][nowCnt] = dis[u][nowCnt] + w;
        pq.push(State(v, dis[v][nowCnt], nowCnt));
      }
    }
  }
}

int main() {
  n = read(), m = read(), k = read();
  // The author prefers numbering from 1 to n, but this problem uses 0 to n - 1, so adjust
  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);  // The graph is undirected
  }
  dijkstra();
  int ans = std::numeric_limits<int>::max();  // Initialize ans to maximum int
  for (int i = 0; i <= k; ++i)
    ans = std::min(ans, dis[t][i]);  // Take the optimal value among all ways to reach the destination
  println(ans);
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用