Posts

00315 Network

Đề:   UVa 00315 Network Abridge: Bài toán tìm Articulation Point điển hình Solution: Using Articulation Point dfs to find, nhớ là lúc đọc input thì + cin >> integer ko đọc '\n'  => dùng thêm  cin.ignore();  + stringstream ss; ss.clear() để xóa đệm, eof,...  + getline (cin,line) thường đi đôi với stringstream. Code:

UVa 11080 Place the Guards

Đề:    11080 Place the Guards Abridge: Có v (vertices) junction (giao lộ) và e (edges) streets (con đường). Một Guard (bảo vệ) đặt tại mỗi vertex (giao lộ) sẽ bảo vệ các junctions và street cận kề. Nếu 2 guards cùng bảo vệ 1 con đường sẽ gây ra đánh nhau. Tìm số bảo vệ ít nhất để bảo vệ tất cả con đường và giao lộ sao cho không xảy ra xung đột. Solution: Bipartite Graph Check + numCC    Vì Graph có nhiều connected component nên: Các CC độc lập với nhau. Với mỗi CC ta lần lượt color vertex đầu = 0 (no guard) hoặc 1 (guards here), nếu cả  2 trường hợp đều return -1 (mâu thuận or ko cover) thì printf("-1"), còn nếu có cái nào được thì lấy cái đó, 2 cái đều được thì lấy min. * Lưu ý: Khi CC chỉ có 1 vertex thì 1 TH duy nhất là phải color nó = 1 (guard here) Code:

UVa 10004 Bicoloring

 Đề:    10004 Bicoloring Abridge: Bipartite Graph Check điển hình Solution: Bipartite Graph Check using BFS Code : 

UVa 11060 Beverages

Đề:   11060 Beverages Abridge: In ra duy nhất 1 topological order với khác biệt: In the case there is no relation between 2 bevarages, Dilbert should start drinking the one that appers first in the input. Khi không có quan hệ giữa 2 loại thức uống thì uống theo thứ tự xuất hiện trong input. Solution: Dùng Kahn 's Algorithms + duyệt theo thứ tự input Tham khảo      http://www.algorithmist.com/index.php/UVa_11060 Code: 

UVa 10305 Ordering Tasks

Đề:     10305 Ordering Tasks Abridge: Xuất ra 1 trật tự topology đúng, có nhiều topological Ordering nhưng chỉ cần xuất ra 1 order là được Solution: Using dfs + lưu lại thứ tự finish các công việc (nodes) , sau đó reverse lại thứ tự đó ta được 1 topological ordering. Chứng minh:   DFS, Topology Sort (38:23) Code:

UVa 00872 Ordering

Đề     00872 Ordering Abridge : In ra tất cả các topological ordering. Solution:  Sử dụng backtracking để sinh hoán vị, nhớ là phải check điều kiện xem tại vị trí ans[i] đó có thể đặt nodes đó hay không.  Một nodes có thể đặt là khi những nodes sau nó (edges[nodes][j]) phải chưa được đặt, ta viết hàm valid() để check. Code: