--- author: nguyencter tags: Numtab0 title: Numtab0 Solution --- $\Huge\text{Numtab0 Solution}$ ------- :::info 📌 Tags: `Matching` `Swap` ✍️ Writer: nguyencter 📋 Content: [TOC] ::: ----- ## Thuật toán Ta thấy để biến đổi mảng thành đường chéo chính đều bằng $1$ thì không cần phải sử dụng thao tác tráo đổi $2$ hàng. Như vậy trên mỗi hàng ta có $1$ vị trí thuộc đường chéo chính và nhiệm vụ của ta là tráo đổi các cột sao cho các vị trí trên đường chéo chính đều bằng 1. Đến đây ta có thể sử dụng cặp ghép để giải quyết bài toán này. Với mỗi hàng ta có thể ghép với các cột mà tại vị trí hàng $i$ và cột $j$ có giá trị là $1$ Xem các hàng và các cột là từng đỉnh để sử dụng cặp ghép và tìm ra với mỗi hàng ta sẽ ghép với cột nào. Sau khi tìm được thứ tự ghép thì ta $Swap$ các cột theo thứ tự đó. Sử dụng mảng đánh dấu để giảm độ phức tạp. ---- Tham khảo code mẫu ở [đây](https://github.com/nguyencter/CODE/blob/main/numtab0.cpp).