Editorial for Bedao OI Contest 4 - OLYMPIAD


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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))~.


Comments

Please read the guidelines before commenting.



  • 0
    ithero  commented on Dec. 18, 2023, 5:52 a.m.

    tham lam cux đc mà nhỉ:)


    • -2
      y  commented on Dec. 18, 2023, 6:00 a.m.

      được gì thế b


      • -1
        ithero  commented on Dec. 18, 2023, 6:06 a.m.

        ý mình là dùng thuật toán tham lam cũng được