Mô hình lát cắt đỉnh

Xây dựng đồ thị có một đỉnh cho mỗi câu và mỗi từ. Với mỗi câu \(S\), nối đỉnh \(S\) với đỉnh của từng từ xuất hiện trong câu.

Xét một đường đi từ câu 0 đến câu 1. Các đỉnh trên đường lần lượt xen kẽ giữa câu và từ. Vì ngôn ngữ của các câu trên đường phải đổi từ tiếng Anh sang tiếng Pháp tại một thời điểm nào đó, ít nhất một từ trên đường phải thuộc cả hai ngôn ngữ.

Ta cần tìm một tập từ nhỏ nhất sao cho mọi đường từ câu 0 tới câu 1 đều đi qua một từ trong tập. Đây chính là bài toán lát cắt đỉnh nhỏ nhất, với điều kiện chỉ được chọn các đỉnh tương ứng với từ.

Chuyển thành lát cắt cạnh

Chuyển bài toán sang lát cắt cạnh trên đồ thị có hướng. Với mỗi từ \(w\), tạo hai đỉnh \(A_w\) và \(B_w\), rồi thêm cung \(A_w\to B_w\) có dung lượng 1.

Với mỗi câu \(S\) chứa \(w\), thêm hai cung \(S\to A_w\) và \(B_w\to S\), đều có dung lượng vô hạn.

Sau đó tìm kích thước lát cắt nhỏ nhất bằng thuật toán luồng cực đại và định lý max-flow min-cut. Mỗi cạnh trong một lát cắt hữu hạn phải là một cung \(A_w\to B_w\), vì đó là những cung duy nhất có dung lượng hữu hạn. Các từ \(w\) tương ứng tạo thành một tập nhỏ nhất các từ song ngữ, chính là lời giải.

Dựa trên phân tích chính thức của Google Code Jam.