Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán rời rạc] Ghép cặp cực đại đồ thị lưỡng phân

    Cho đồ thị lưỡng phân với phía trái gồm nLn_LnL​ đỉnh (0..nL−10..n_L-10..nL​−1) và phía phải gồm nRn_RnR​ đỉnh (0..nR−10..n_R-10..nR​−1). Hãy tìm lực lượng ghép cặp cực đại — số cạnh lớn nhất sao cho không có hai cạnh chung đỉnh. Theo định lý König, trên đồ thị lưỡng phân, lực lượng này bằng số đỉnh nhỏ nhất phủ hết mọi cạnh. Kết quả là một số nguyên xác định.

    • Định dạng đầu vào:

      Dòng đầu: nLn_LnL​, nRn_RnR​, mmm. mmm dòng sau, mỗi dòng u vu\ vu v nghĩa là có cạnh giữa đỉnh trái uuu và đỉnh phải vvv.

    • Ràng buộc đầu vào:

      1≤nL,nR≤5001 \le n_L,n_R \le 5001≤nL​,nR​≤500, 0≤m≤nL⋅nR0 \le m \le n_L\cdot n_R0≤m≤nL​⋅nR​.

    • Định dạng đầu ra:

      Một dòng: lực lượng ghép cặp cực đại.

    Ví dụ:

    Đầu vào:

    3 3 4
0 0
0 1
1 0
2 2

    Đầu ra:

    3

    Giải thích:

    Có thể ghép $0\!-\!1$, $1\!-\!0$, $2\!-\!2$ — ghép cặp cực đại lực lượng 3.

    Đang tải editor...