Chặt nhị phân đáp án. Với \(W\), cần kiểm tra xem ta có thể khôi phục bảng để có độ ổn định \(\leq W\) hay không?

Để đạt được độ ổn định là \(W\), số lượng số \(1\) trên mỗi hàng / cột phải nằm trong đoạn \([L,R]\).

Mỗi ô \((r,c)\) của bảng tạo nên một ràng buộc giữa hàng \(r\) và cột \(c\).
Để xây dựng đồ thị ta tạo ra \(m\) đỉnh đại diện cho \(m\) hàng, \(n\) đỉnh đại diện cho \(n\) cột, hai đỉnh nguồn (source) và đích (sink) như mạng trong mọi bài luồng khác.

Ngoài ra với luồng 2 cận thì ta sẽ cần thêm 2 đỉnh \(S', T'\) nữa. Các bạn có thể tham khảo DSAP Textbook của thầy Lê Minh Hoàng để hiểu cách đưa bài toán luồng cận dưới về bài toán luồng không có cận dưới.

• Nếu ô có giá trị là 1 : thêm một cung có cận dưới là \(1\), thông lượng là \(1\) từ hàng r tới cột c
• Nếu ô có giá trị là * : thêm một cung có thông lượng là \(1\) từ hàng r tới cột c

Gọi rlow, rhigh là số lượng số \(1\) ít nhất và nhiều nhất có thể chấp nhận được cho mỗi hàng. Tương tự ta đặt biến clow, chigh cho mỗi cột.

Lúc này ta sẽ thêm cung từ source tới mọi hàng, cung này có cận dưới là rlow, thông lượng là rhigh.

Sau đó ta thêm cung từ mọi cột tới sink, cung này có cận dưới là clow, thông lượng là chigh.