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

    solution

    Đề bài: [Giải thuật] Cây khung nhỏ nhất Kruskal

    Cho đồ thị vô hướng nnn đỉnh, mmm cạnh trọng số. Tìm tổng trọng số của cây khung nhỏ nhất (MST). Nếu đồ thị không liên thông, in -1.

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

      Dòng đầu: nnn, mmm. mmm dòng: uuu, vvv, www.

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

      1≤n≤1051 \le n \le 10^51≤n≤105, 0≤m≤2⋅1050 \le m \le 2\cdot10^50≤m≤2⋅105, 0≤w≤1090 \le w \le 10^90≤w≤109.

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

      Một số nguyên: tổng trọng số MST, hoặc -1.

    Ví dụ:

    Đầu vào:

    4 5
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5

    Đầu ra:

    6

    Giải thích:

    Chọn các cạnh trọng số 1,2,3 nối đủ 4 đỉnh; tổng = 6, bỏ cạnh 4 và 5.

    Đang tải editor...