Solutions of Build the board

Select solution language

tcmduc Created at 3 likes

Ta dựng đồ thị như sau : với đỉnh nguồn $S$ ta nối với các đỉnh ảo tượng trưng cho các hàng với lưu lượng là tổng của hàng đó, mỗi hàng nối với các cột với lưu lượng là $1$, các cột này lại nối với đỉnh thu $T$ với lưu lượng bằng tổng của cột đó Để bảng được đảm bảo theo thứ tự từ điển nhỏ nhất, ta xét từng hàng từ $1$ đến $n$, rồi xét từng ô từ ô thứ $n$ đến ô $1$ của hàng đó, ta thử giả sử ô đó là số $1$, thử dựng lại mạng luồng sau khi cắt bỏ cạnh là giao của hàng và cột ở ô này, và giảm tổng hàng và tổng cột giao ở ô này đi 1,và chạy luồng Nếu luồng cực đại tìm được = tổng phần bảng còn lại cần điền, thì điền ô đang xét là $1$. Còn nếu không phải thì điền $0$, cộng lại tổng hàng và tổng cột giao ở ô này $=>$ Bảng tìm được sau cùng chính là bảng có thứ tự từ điển nhỏ nhất thỏa mãn