Hướng dẫn giải của Bedao OI Contest 4 - OLYMPIAD
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Ta thêm đỉnh ảo ~0~ nối với tất cả các vđv với trọng số ~0~.
Các đường tăng luồng có dạng ~u_1 - v_1 - u_2 - v_2 - \cdots - u_l - v_l - u_{l + 1}~ (~l \le m~ và ~u_{l + 1} = 0~) với ~u_i~ là các nội dùng, ~v_i~ là các vđv.
~u_i - v_i~ là các cạnh chưa chọn và ~v_i - u_{i + 1}~ là các cạnh đã chọn.
Ta sẽ duy trì tập hợp ~S[u_1][u_2]~ các hiệu ~c[v][u_1] - c[v][u_2]~ với mọi cặp (~u_1, u_2~) (cạnh ~v - u_1~ chưa được chọn và cạnh ~v - u_2~ đã được chọn).
Khi đó để tìm đường tăng luồng ta chỉ cần tìm đường đi dài nhất trên đồ thị ~k~ đỉnh với ~w(u_1, u_2) = \min(S[u_1][u_2])~. Có thể dùng Floyd hoặc Bellman-Ford trong ~\mathcal{O}(m^3)~
Vì đường tăng luồng có độ dài tối đa là ~2k~ nên ta có thể lưu các tập ~S~ bằng std::set và cập nhật trong ~\mathcal{O}(m^2 \log_2 n)~
Độ phức tạp tổng là ~\mathcal{O}(n \cdot (m^3 + m^2 \log_2 n))~.
Bình luận
tham lam cux đc mà nhỉ:)
được gì thế b
ý mình là dùng thuật toán tham lam cũng được