Cấu trúc dữ liệu và Giải thuật Bài 139: Mạng luồng có ràng buộc dung lượng dưới (Circulation with Demands and Lower Bounds) - Khử cận dưới bằng đỉnh siêu nguồn và siêu đích.

Trong các bài toán mạng luồng kinh điển (như Dinic hay Edmonds-Karp), mỗi cạnh $e = (u, v)$ luôn có cận dưới bằng $0$ ($0 \le f(e) \le c(e)$) và mọi đỉnh trung gian đều tuân thủ định luật bảo toàn luồng nghiêm ngặt (tổng luồng vào bằng tổng luồng ra). Tuy nhiên, các hệ thống công nghiệp và bài toán phân bổ tài nguyên thực tế thường áp đặt thêm hai ràng buộc khắt khe:

1. Ràng buộc dung lượng dưới (Lower Bounds): Mỗi tuyến đường hoặc ống dẫn bắt buộc phải duy trì một lượng lưu lượng tối thiểu $l(e) > 0$ (ví dụ: cam kết băng thông tối thiểu CIR, áp suất duy trì đường ống). Khi đó: $l(e) \le f(e) \le c(e)$.

2. Nhu cầu / Khả năng cung cấp tại từng đỉnh (Node Demands/Supplies): Một số đỉnh là nơi tiêu thụ (Demand: cần nhận thêm luồng) hoặc nơi sản xuất (Supply: cần đẩy luồng đi), khiến tổng luồng vào và ra tại đỉnh đó không triệt tiêu về $0$.

Bài toán tìm luồng thỏa mãn toàn bộ các điều kiện trên được gọi là bài toán Luồng tuần hoàn có nhu cầu và cận dưới (Circulation with Demands and Lower Bounds). Thuật toán quy đổi bài toán phức tạp này về mạng luồng chuẩn bằng cách khử cận dưới và thiết lập cặp siêu nguồn ($S^*$) - siêu đích ($T^*$), giải quyết trọn vẹn trong thời gian $O(V^2 E)$ bằng thuật toán Dinic.

1. Định nghĩa bài toán Luồng tuần hoàn có Nhu cầu và Cận dưới

Cho đồ thị có hướng $G = (V, E)$. Với mỗi cạnh $e = (u, v) \in E$, ta có:

• Cận dưới (Lower bound): $l(e) \ge 0$.

• Cận trên (Capacity): $c(e) \ge l(e)$.

Mỗi đỉnh $u \in V$ có một chỉ số nhu cầu $d(u)$:

• $d(u) > 0$: Đỉnh $u$ là đỉnh tiêu thụ (cần lượng luồng vào ròng bằng $d(u)$).

• $d(u) < 0$: Đỉnh $u$ là đỉnh sản xuất (cần lượng luồng ra ròng bằng $-d(u)$).

• $d(u) = 0$: Đỉnh trung gian bảo toàn luồng thông thường.

Một hàm luồng $f: E \to \mathbb{R}^+$ được gọi là luồng khả thi (Feasible Circulation) nếu thỏa mãn đồng thời hai điều kiện:

1. Ràng buộc dung lượng:

   $$\forall e \in E: \quad l(e) \le f(e) \le c(e)$$

2. Bảo toàn luồng tại từng đỉnh (Conservation with Demands):

   $$\forall u \in V: \quad \sum_{e \in \text{in}(u)} f(e) - \sum_{e \in \text{out}(u)} f(e) = d(u)$$

Điều kiện cần để tồn tại nghiệm: Tổng nhu cầu trên toàn mạng phải bằng $0$:

$$\sum_{u \in V} d(u) = 0$$

Nếu tổng nhu cầu khác $0$, hệ thống chắc chắn vô nghiệm vì tổng luồng sản xuất không cân bằng với tổng luồng tiêu thụ.

2. Kỹ thuật toán học Khử cận dưới (Lower Bound Elimination)

Để đưa các cạnh về dạng luồng tiêu chuẩn có cận dưới bằng $0$, ta thực hiện phép đổi biến cho từng cạnh $e$:

$$f'(e) = f(e) - l(e)$$

Khi đó, miền giá trị của luồng mới $f'(e)$ trở thành:

$$0 \le f'(e) \le c(e) - l(e)$$

Dung lượng mới của cạnh $e$ trên mạng phụ trợ là:

$$c'(e) = c(e) - l(e)$$

Ảnh hưởng của phép đổi biến lên cân bằng đỉnh

Thay $f(e) = f'(e) + l(e)$ vào phương trình bảo toàn luồng tại mỗi đỉnh $u$:

$$\sum_{e \in \text{in}(u)} (f'(e) + l(e)) - \sum_{e \in \text{out}(u)} (f'(e) + l(e)) = d(u)$$

Chuyển các hằng số $l(e)$ sang vế phải:

$$\sum_{e \in \text{in}(u)} f'(e) - \sum_{e \in \text{out}(u)} f'(e) = d(u) - \sum_{e \in \text{in}(u)} l(e) + \sum_{e \in \text{out}(u)} l(e)$$

Đặt độ mất cân bằng mới của đỉnh $u$ là $\Delta(u)$:

$$\Delta(u) = d(u) - \sum_{e \in \text{in}(u)} l(e) + \sum_{e \in \text{out}(u)} l(e)$$

Phương trình bảo toàn luồng đối với biến mới $f'$ trở thành:

$$\sum_{e \in \text{in}(u)} f'(e) - \sum_{e \in \text{out}(u)} f'(e) = \Delta(u)$$

3. Xây dựng Mạng phụ trợ với Siêu nguồn ($S^*$) và Siêu đích ($T^*$)

Đại lượng $\Delta(u)$ phản ánh sự chênh lệch giữa luồng vào và luồng ra cần có của $u$ trong mạng mới:

1. Trường hợp $\Delta(u) > 0$ (Đỉnh thiếu luồng vào):

   • Lượng luồng đi vào $u$ cần nhiều hơn lượng luồng đi ra là $\Delta(u)$ đơn vị.

   • Để giải tỏa lượng luồng dư thừa này về trạng thái bảo toàn luồng tiêu chuẩn, ta thêm một cung nối từ đỉnh $u$ đến siêu đích $T^*$ với dung lượng:

     $$c'(u, T^*) = \Delta(u)$$

2. Trường hợp $\Delta(u) < 0$ (Đỉnh thiếu luồng ra):

   • Lượng luồng đi ra khỏi $u$ cần nhiều hơn lượng luồng đi vào là $-\Delta(u)$ đơn vị.

   • Ta bổ sung nguồn cung cấp từ siêu nguồn $S^*$ bằng cách nối một cung từ $S^*$ đến $u$ với dung lượng:

     $$c'(S^*, u) = -\Delta(u)$$

           Mạng ban đầu (có l(e) và d(u)):
                     l(e) <= f(e) <= c(e)
           (u) --------------------------------> (v)
           d(u)                                  d(v)

                                ||
                     [Khử cận dưới & Tạo S*, T*]
                                ||
                                v
           Mạng phụ trợ G' (cận dưới = 0):
                   c'(e) = c(e) - l(e)
           (u) --------------------------------> (v)
            ^                                     |
            | c' = -Δ(u)                          | c' = Δ(v)
           [S*]                                  [T*]
         (Nếu Δ < 0)                           (Nếu Δ > 0)

Định lý Khả thi (Feasibility Theorem)

Chạy thuật toán Luồng cực đại từ $S^*$ đến $T^*$ trên đồ thị phụ trợ $G'$:

• Luồng khả thi $f$ trên mạng ban đầu tồn tại khi và chỉ khi mọi cung đi ra từ $S^*$ (hoặc tương đương, mọi cung đi vào $T^*$) đều bị bão hòa hoàn toàn:

  $$\text{MaxFlow}(S^*, T^*) = \sum_{u: \Delta(u) < 0} (-\Delta(u)) = \sum_{u: \Delta(u) > 0} \Delta(u)$$

• Nếu điều kiện trên thỏa mãn, luồng thực tế trên từng cạnh ban đầu được khôi phục bằng:

  $$f(e) = f'(e) + l(e)$$

4. Biến thể: Luồng khả thi $s-t$ có Cận dưới ($s-t$ Feasible Flow)

Trong bài toán mạng có nguồn $s$ và đích $t$ cố định (thay vì luồng tuần hoàn tự do), ta chỉ cần chuyển đổi bằng cách:

• Thêm một cạnh ảo nối ngược từ $t$ về $s$ với cận dưới $0$ và cận trên vô cùng:

  $$e_{\text{loop}} = (t \to s), \quad l(e_{\text{loop}}) = 0, \quad c(e_{\text{loop}}) = \infty$$

• Đặt nhu cầu $d(u) = 0$ cho tất cả các đỉnh (kể cả $s$ và $t$).

• Toàn bộ luồng chảy từ $s \to t$ được tuần hoàn ngược trở lại $s$, quy bài toán về bài toán Circulation thông thường.

5. Hiện thực hóa Thuật toán bằng Golang

Chương trình Golang dưới đây cài đặt hoàn chỉnh:

1. Thuật toán Dinic tiêu chuẩn cho mạng có cận dưới bằng $0$.

2. Module CirculationSolver thực hiện khử cận dưới, tính $\Delta(u)$, nối cạnh tới $S^*, T^*$ và khôi phục luồng gốc.

Go

package main

import (
	"fmt"
	"math"
)

const INF = math.MaxInt64 / 4

// Cạnh trong đồ thị thặng dư Dinic
type FlowEdge struct {
	to   int
	rev  int
	cap  int64
	flow int64
}

type Dinic struct {
	n     int
	adj   [][]FlowEdge
	level []int
	ptr   []int
}

func NewDinic(n int) *Dinic {
	return &Dinic{
		n:     n,
		adj:   make([][]FlowEdge, n),
		level: make([]int, n),
		ptr:   make([]int, n),
	}
}

func (d *Dinic) AddEdge(from, to int, cap int64) int {
	fwd := FlowEdge{to: to, rev: len(d.adj[to]), cap: cap, flow: 0}
	bwd := FlowEdge{to: from, rev: len(d.adj[from]), cap: 0, flow: 0}
	d.adj[from] = append(d.adj[from], fwd)
	d.adj[to] = append(d.adj[to], bwd)
	return len(d.adj[from]) - 1 // Trả về index của cạnh xuôi
}

func (d *Dinic) bfs(s, t int) bool {
	for i := 0; i < d.n; i++ {
		d.level[i] = -1
	}
	d.level[s] = 0
	queue := []int{s}

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]

		for _, e := range d.adj[u] {
			if e.cap-e.flow > 0 && d.level[e.to] == -1 {
				d.level[e.to] = d.level[u] + 1
				queue = append(queue, e.to)
			}
		}
	}
	return d.level[t] != -1
}

func (d *Dinic) dfs(u, t int, pushed int64) int64 {
	if pushed == 0 || u == t {
		return pushed
	}

	for ; d.ptr[u] < len(d.adj[u]); d.ptr[u]++ {
		e := &d.adj[u][d.ptr[u]]
		tr := e.to

		if d.level[u]+1 != d.level[tr] || e.cap-e.flow == 0 {
			continue
		}

		pushVal := pushed
		if e.cap-e.flow < pushVal {
			pushVal = e.cap - e.flow
		}

		trPushed := d.dfs(tr, t, pushVal)
		if trPushed == 0 {
			continue
		}

		e.flow += trPushed
		d.adj[tr][e.rev].flow -= trPushed
		return trPushed
	}
	return 0
}

func (d *Dinic) MaxFlow(s, t int) int64 {
	var totalFlow int64 = 0
	for d.bfs(s, t) {
		for i := 0; i < d.n; i++ {
			d.ptr[i] = 0
		}
		for {
			pushed := d.dfs(s, t, INF)
			if pushed == 0 {
				break
			}
			totalFlow += pushed
		}
	}
	return totalFlow
}

// Cấu trúc cạnh của bài toán ban đầu
type OriginalEdge struct {
	from, to int
	lower    int64
	upper    int64
	edgeIdx  int // Lưu vị trí cạnh trong đồ thị Dinic
}

type CirculationSolver struct {
	n       int
	edges   []OriginalEdge
	demands []int64
}

func NewCirculationSolver(n int) *CirculationSolver {
	return &CirculationSolver{
		n:       n,
		demands: make([]int64, n),
	}
}

func (cs *CirculationSolver) AddEdge(from, to int, lower, upper int64) {
	cs.edges = append(cs.edges, OriginalEdge{
		from:  from,
		to:    to,
		lower: lower,
		upper: upper,
	})
}

func (cs *CirculationSolver) SetDemand(node int, demand int64) {
	cs.demands[node] = demand
}

// Solve tìm luồng khả thi. Trả về (feasible, actualFlows)
func (cs *CirculationSolver) Solve() (bool, []int64) {
	// Kiểm tra điều kiện cần: tổng nhu cầu phải bằng 0
	var sumDemands int64 = 0
	for _, d := range cs.demands {
		sumDemands += d
	}
	if sumDemands != 0 {
		return false, nil
	}

	// 1. Tính toán delta cho từng đỉnh
	delta := make([]int64, cs.n)
	copy(delta, cs.demands)

	for _, e := range cs.edges {
		delta[e.from] += e.lower // Luồng ra khỏi from
		delta[e.to] -= e.lower   // Luồng vào to
	}

	// 2. Thiết lập siêu nguồn S* và siêu đích T*
	sStar := cs.n
	tStar := cs.n + 1
	dinic := NewDinic(cs.n + 2)

	// Thêm các cạnh ban đầu đã khử cận dưới: dung lượng c' = upper - lower
	for i := range cs.edges {
		e := &cs.edges[i]
		e.edgeIdx = dinic.AddEdge(e.from, e.to, e.upper-e.lower)
	}

	// 3. Nối các cạnh từ S* hoặc tới T*
	var expectedFlow int64 = 0
	for i := 0; i < cs.n; i++ {
		if delta[i] > 0 {
			// Cần luồng đi ra tới T*
			dinic.AddEdge(i, tStar, delta[i])
		} else if delta[i] < 0 {
			// Cần luồng đi vào từ S*
			dinic.AddEdge(sStar, i, -delta[i])
			expectedFlow += -delta[i]
		}
	}

	// 4. Chạy Max-Flow trên mạng phụ trợ
	maxFlow := dinic.MaxFlow(sStar, tStar)

	if maxFlow != expectedFlow {
		return false, nil // Không bão hòa hết các cạnh của S*
	}

	// 5. Khôi phục luồng thực tế: f(e) = f'(e) + lower(e)
	actualFlows := make([]int64, len(cs.edges))
	for i, e := range cs.edges {
		fPrime := dinic.adj[e.from][e.edgeIdx].flow
		actualFlows[i] = fPrime + e.lower
	}

	return true, actualFlows
}

func main() {
	// Mô phỏng bài toán Luồng tuần hoàn 4 đỉnh (0 đến 3) có cận dưới và nhu cầu
	// Nhu cầu: Đỉnh 0 là nơi sản xuất (-3), Đỉnh 3 là nơi tiêu thụ (+3), Đỉnh 1 & 2 trung gian (0)
	n := 4
	solver := NewCirculationSolver(n)

	solver.SetDemand(0, -3) // Supply 3 đơn vị
	solver.SetDemand(1, 0)
	solver.SetDemand(2, 0)
	solver.SetDemand(3, 3) // Demand 3 đơn vị

	// Các cạnh: (from, to, lower, upper)
	solver.AddEdge(0, 1, 1, 3) // 0 -> 1: [1, 3]
	solver.AddEdge(0, 2, 1, 2) // 0 -> 2: [1, 2]
	solver.AddEdge(1, 2, 0, 2) // 1 -> 2: [0, 2]
	solver.AddEdge(1, 3, 1, 4) // 1 -> 3: [1, 4]
	solver.AddEdge(2, 3, 1, 3) // 2 -> 3: [1, 3]

	feasible, flows := solver.Solve()

	if !feasible {
		fmt.Println("Không tồn tại luồng khả thi thỏa mãn cận dưới và nhu cầu!")
		return
	}

	fmt.Println("Tìm thấy luồng khả thi thành công:")
	for i, e := range solver.edges {
		fmt.Printf("Cạnh %d -> %d: Luồng = %d (Cận: [%d, %d])\n",
			e.from, e.to, flows[i], e.lower, e.upper)
	}

	// Kiểm tra bảo toàn luồng tại từng đỉnh
	fmt.Println("\nKiểm tra cân bằng luồng tại từng nút:")
	netFlow := make([]int64, n)
	for i, e := range solver.edges {
		netFlow[e.to] += flows[i]
		netFlow[e.from] -= flows[i]
	}
	for i := 0; i < n; i++ {
		fmt.Printf("Đỉnh %d: Luồng vào - Luồng ra = %d (Kỳ vọng Demand = %d)\n",
			i, netFlow[i], solver.demands[i])
	}
}

6. Phân tích độ phức tạp

7. Ứng dụng thực tế

• Lập lịch phân công ca trực (Nurse / Crew Scheduling with Minimum Staffing): Mỗi ca trực bắt buộc phải có tối thiểu $l_j$ nhân viên và tối đa $c_j$ nhân viên. Mỗi nhân viên có số ca làm tối thiểu và tối đa trong tuần. Mô hình Circulation with Lower Bounds giải quyết bài toán này trực tiếp.

• Tái cân bằng xe đạp/xe công nghệ (Bike-Sharing / Fleet Rebalancing): Các trạm xe có lượng xe thặng dư hoặc thiếu hụt sau giờ cao điểm (demands). Các xe tải trung chuyển di chuyển giữa các trạm với số lượng xe vận chuyển tối thiểu để tối ưu chi phí nhiên liệu.

• Ma trận số nguyên với tổng hàng và tổng cột bị chặn hai đầu (Matrix Rounding / Bounded Sums): Khôi phục ma trận số nguyên từ bảng dữ liệu thống kê sao cho tổng các phần tử trên mỗi hàng và cột nằm trong các khoảng $[R_{\min}, R_{\max}]$ và $[C_{\min}, C_{\max}]$.