VOI 11 Bài 6 - Nâng cấp mạng

Xem dạng PDF

Gửi bài giải


Điểm: 0,28 (OI)
Giới hạn thời gian: 0.6s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
VOI 2011
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một hệ thống gồm ~n~ máy tính đánh số từ ~1~ đến ~n~ được kết nối thành một mạng bởi ~m~ đoạn cáp mạng đánh số từ ~1~ đến ~m~. Đoạn cáp mạng thứ ~i~ có thông lượng ~w_{i}~ kết nối hai máy ~u_{i}~ , ~v_{i}~ cho phép truyền dữ liệu theo cả hai chiều giữa hai máy này.

Một dãy các máy ~x_{1} , x_{2} , ..., x_{p}~ trong đó giữa hai máy ~x_{j}~ và ~x_{j+1} \;(j = 1, 2, ..., p-1)~ có đoạn cáp nối được gọi là một đường truyền tin từ máy ~x_{1}~ tới máy ~x_{p}~ . Thông lượng của đường truyền tin được xác định như là thông lượng nhỏ nhất trong số các thông lượng của các đoạn cáp mạng trên đường truyền. Giả thiết là mạng được kết nối sao cho có đường truyền tin giữa hai máy bất kì và giữa hai máy có không quá một đoạn cáp mạng nối chúng.

Người ta muốn nâng cấp mạng bằng cách tăng thông lượng của một số đoạn cáp nối trong mạng. Để tăng thông lượng của mỗi đoạn cáp mạng thêm một lượng ~d \;(d > 0)~ ta phải trả một chi phí đúng bằng ~d~. Việc nâng cấp mạng phải đảm bảo là sau khi hoàn tất, thông lượng của mỗi đoạn cáp mạng ~i~ đều bằng thông lượng của đường truyền tin có thông lượng lớn nhất từ máy ~u_{i}~ tới máy ~v_{i}~ .

Yêu cầu: Tìm phương án nâng cấp các đoạn cáp mạng sao cho tổng chi phí nâng cấp là nhỏ nhất.

Input

  • Dòng thứ nhất: Chứa hai số nguyên dương ~n, m \;(n, m \leq 10^5)~.
  • Dòng thứ ~i~ trong số ~m~ dòng tiếp theo chứa ba số nguyên dương ~u_{i} , v_{i} , w_{i}\; (w_{i} \leq 10^6), \;i = 1, 2, ..., m~.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi ra một số nguyên duy nhất là tổng chi phí nâng cấp theo phương án tìm được.

Giới hạn

50% số test ứng với 50% số điểm của bài có ~n \leq 100~.

Sample Input

6 7
1 2 6
1 3 5
2 4 3
3 4 9
4 5 4
4 6 8
5 6 7

Sample Output

5

Note

image


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 2
    minhkochamhoc  đã bình luận lúc 26, Tháng 6, 2025, 15:13

    solve:

    giải thích đề và ý tưởng:

    • đầu tiên hãy chú ý đề nói rằng : thông lượng của đường truyền tin là thông lượng nhỏ nhất trong số các thông lượng đó
    • bây giờ ta cần cập nhật 1 số đoạn cáp sau cho khi xét đường truyền trực tiếp từ u -> v ta đảm bảo rằng trọng số của nó lớn hơn hoặc bằng thông lượng lớn nhất khi đi từ u -> v . hay nói cách khác khi xét đường đi trực tiếp từ u -> v (có thông lượng w1) ta so sánh thông lượng của nó so với thông lượng lớn nhất của đường đi khác khi đi từ u->v (có thông lượng w2) rồi xem nếu đường đi trực tiếp đó có thông lượng bé hơn ta phải cập nhật nó lên và chịu chi phí là d = w2 - w1.
    • ta có thể xét hai ví dụ sau để dễ hiểu hơn ( theo hình vẽ của đề ) :
    • VD 1: xét đường đi trực tiếp từ 1->2 trên đồ thị có thông lượng là 6 (do có 1 cạnh duy nhất) , ta so sánh với 1 đường đi khác từ 1->2 đó là 1->3->4->2 có thông lượng là 5 (nhìn lại định nghĩa thông lượng) ta thấy rằng do thông lượng của đường đi trực tiếp lớn hơn nên ta ko phải cập nhật đoạn này .
    • VD 2: xét đường đi trực tiếp từ 2->4 có thông lượng là 3 , 1 đường đi khác là 2->1->3->4 có thông lượng là 5 , do thông lượng trực tiếp bé hơn thông lượng của đường đi kia ta cần nâng cấp đường đi trực tiếp này lên vào chịu chi phí là :5-3=2.
    • sau khi hiểu được đề bài ta sẽ có ý tưởng như sau :
    • đầu tiên ta cần xây dựng 1 cây khung ưa trọng số nặng vì 2 lý do sau : do là cây khung nên ta đảm bảo khi xét 2 đỉnh bất kì trong n đỉnh trên ta chắc chắn sẽ có đường đi giữa 2 đỉnh này , còn ưa trọng số nặng là vì để khi xét đường đi giữa u -> v xem có nên cập nhật ko ta đảm bảo nếu lấy thông lượng trên cây khung này nó chắc chắn sẽ là thông lượng lớn nhất so với những đường đi giữa u->v khác do đã lấy những trọng số lớn nhất có thể để xây cây khung.
    • sau khi đã có cây khung ta sẽ nghĩ tới giải pháp nào để có thể lấy được thông lượng trên cây khung khi đi từ u->v , và vì ta đang xét tới cây khung nên giải pháp đơn giải ta có thể nghĩ tới là build LCA + rmq để xử lý nhanh chỉ với O(log(n)) do nó là cây mà
    • cuối cùng ta chỉ cần duyệt lại danh sách cạnh mà đề bài cho để xem là cạnh nối trực tiếp giữa 2 đỉnh u,v nào đó có cần cập nhật hay ko , cộng lại hết các chi phí cập nhật và đó sẽ là kết quả của ta
    • đây là code tớ : hehehe
    • "Chắc chắn rằng mọi khó khăn chỉ là thử thách để bạn vươn lên mạnh mẽ hơn. Hãy tiếp tục cố gắng, thành công sẽ đến với những ai không bỏ cuộc! 🍀"

  • -4
    minhduca2k53  đã bình luận lúc 8, Tháng 5, 2025, 10:18

    Skibidi toilet


  • 3
    vendettas  đã bình luận lúc 22, Tháng 3, 2025, 6:26

    đề voi khó hiểu vaiz :)


  • -20
    minhnhut  đã bình luận lúc 19, Tháng 8, 2024, 8:37

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.