VOI 21 Bài 6 - Chia nhóm

View as PDF

Submit solution


Points: 1.50 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một công ty có ~n~ nhân viên, các nhân viên được đánh số từ ~1~ đến ~n~. Công ty đang chuẩn bị kỉ niệm 100 năm thành lập và dự định tổ chức nhiều hoạt động ngoại khóa. Một hoạt động được nhiều người mong đợi đòi hỏi phải chia ~n~ nhân viên thành hai nhóm. Qua thu thập thông tin, Ban tổ chức biết được ràng, nhân viên ~i~ không muốn cùng với nhân viên ~p_i~ ~(1 \le i \le n)~. Dựa trên yêu cầu của mỗi nhân viên, Ban tổ chức muốn tìm một cách chia ~n~ nhân viên thành hai nhóm mà nhân viên ~i~ khác nhóm với nhân viên ~p_i~. Trường hợp không tồn tại cách chia thỏa mãn, Ban tổ chức sẽ phải thuyết phục một số người chấp nhận cùng nhóm với người mà họ không muốn, thời gian để thuyết phục nhân viên ~i~ cùng nhóm với nhân viên ~p_i~ là ~w_i~.

Theo thông tin mà Ban tổ chức mới nhận được thì dữ liệu thu thập có thể chưa đầy đủ, có thể có thêm một cặp nhân viên ~(u, v)~ không muốn cùng một nhóm. Ban tổ chức đã đưa ra một danh sách gồm ~m + 1~ giả định: Giả định 0, không có thêm cặp nào; giả định thứ ~k~ ~(1 \le k \le m)~ là có thêm cặp nhân viên ~(u_k, v_k)~ không muốn cùng nhóm với nhau và nếu muốn cả hai nhân viên ~u_k~ và ~v_k~ đồng ý cùng nhóm thì phải mất thời gian thuyết phục cặp ~(u_k, v_k)~ là ~t_k~.

Yêu cầu: Với mỗi giả định, hãy giúp Ban tổ chức tính toán tổng thời gian thuyết phục ít nhất để có thể chia ~n~ nhân viên thành hai nhóm.

Dữ liệu

Vào từ đầu vào chuẩn (không phải file TEAMUP.INP):

  • Dòng đầu chứa số nguyên dương ~n~ ~(n \le 10^5)~;
  • Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa hai số nguyên dương ~p_i, w_i~ ~(p_i \le n; p_i \ne i; w_i \le 10^9)~;
  • Dòng tiếp theo theo chứa số nguyên không âm ~m~ ~(m \le 10^5)~;
  • Dòng thứ ~k~ trong số ~m~ dòng tiếp theo chứa ba số nguyên dường ~u_k, v_k, t_k~ ~(u_k, v_k \le n; u_k \ne v_k; u_k \ne p_{v_k}; v_k \ne p_{u_k}; t_k \le 10^9)~;

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra đầu ra chuẩn (không phải file TEAMUP.OUT) gồm ~m + 1~ dòng, mỗi dòng một số nguyên là tổng thời gian thuyết phục ít nhất lần lượt tương ứng cho từng giả định.

Ràng buộc

  • Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn: ~m = 0, n \le 1000~ và dãy ~p_1, p_2, \dotsc, p_n~ là hoán vị của ~1, 2, \dotsc, n~;
  • ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn: ~m = 0, n \le 1000~;
  • ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thỏa mãn: ~m \le 1000, n \le 1000~;
  • ~15\%~ số test khác ứng với ~15\%~ số điểm của bài thỏa mãn: dãy ~p_1, p_2, \dotsc, p_n~ là hoán vị của ~1, 2, \dotsc, n~;
  • ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input
5
2 3
3 4
4 1
5 3
1 2
2
1 4 2
1 3 1
Output
1
2
2
Giải thích
  • Giả định 0: Thuyết phục nhân viên 3 mất 1 đơn vị thời gian. Khi đó, có thể chia thành hai nhóm ~(1, 3, 4)~ và ~(2, 5)~.
  • Giả định 1: Thuyết phục nhân viên 5 mất 2 đơn vị thời gian. Khi đó, có thể chia thành hai nhóm ~(1, 3, 5)~ và ~(2, 4)~.
  • Giả định 2: Thuyết phục nhân viên 3 mất 1 đơn vị thời gian và thuyết phục cặp ~(1, 3)~ mất 1 đơn vị thời gian. Khi đó, có thể chia thành hai nhóm ~(1, 3, 4)~ và ~(2, 5)~.

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.


There are no comments at the moment.