[LẬP TRÌNH NÂNG CAO] buổi 11 - Bài toán Luồng trên mạng

[sonnt]

Nội dung:

1. Bài toán
2. Thuật toán For-Fulkerson/Edmonds-Karp
3. Thuật toán Dinic
4. Tổng hợp một số thuật toán tìm luồng cực đại
5. Các bài toán thường gặp:

• Xác định lát cắt hẹp nhất
• Luồng trên mạng có nhiều đỉnh phát, nhiều đỉnh thu
• Cặp ghép trên đồ thị 2 phía
• Luồng bị chặn 2 phía
• Luồng trên mạng với đỉnh có khả năng thông qua bị giới hạn

Bài giảng đính kèm

[sonnt]

Vì hôm nay có bài tập lấy điểm A1 nhưng các bạn không có mặt đầy đủ nên tôi quyết định bài tập lấy điểm sẽ là bài MOBIVINA trên spoj (https://www.spoj.com/problems/MOBIVINA/). Các bạn làm bài, nộp online và gửi minh chứng vào thread này trước 0g00 ngày thứ 6 (3/8) nhé. Bạn còn cần gửi source code bài làm vào email của tôi. Các bạn không gửi kết quả ở đây hay không gửi source code cho tôi qua mail đều được 0 điểm bài tập này.

Lưu ý: không gửi source code ở đây

Tuần sau, chúng ta vẫn tiếp tục với bài học về luồng trên mạng.

[17520015]

dạ, em gửi bài !

[17520584]

dạ, em gửi bài !

[16521170]

Thầy cho em gửi bài ạ

[sonnt]

dạ, em gửi bài !

KHông thấy gửi source code qua email của tui, và sao nick của em lại không hiện ra trên hình ???

[toannv]

Chào các bạn!
Do forum bị restore nên bạn nào đã up bài thì up lại nhé,
Cảm ơn các bạn!