Nguồn: Đề thi học sinh giỏi quốc gia 2013
Tổng công ty Z gồm N công ty con, đánh số từ 1-N.
Mỗi công ty con có một máy chủ. Để đảm bảo truyền tin giữa các công ty, Z thuê M
đường truyền tin để kết nối N máy chủ thành một mạng máy tính của Tổng công ty.
Không có 2 đường truyền nối cùng 1 cặp máy chủ. Đường truyền i nối máy chủ của
2 công ty ui, vi có chi phí là wi. Mạng
máy tính có tính thông suốt, nghĩa là từ một máy chủ có thể truyền
tin đến một máy chủ bất kì khác bằng đường truyền trực tiếp hoặc qua nhiều
đường trung gian.
Một đường truyền gọi là không tiềm năng nếu như :
một mặt, việc loại bỏ đường truyền này không làm mất tính thông suốt; mặt khác,
nó phải có tính không tiềm năng, nghĩa là không thuộc bất cứ mạng con thông
suốt gồm N máy chủ và N-1 đường truyền tin với tổng chi phí thuê bao nhỏ nhất
nào của mạng máy tính.
Trong thời gian tới, chi
phí thuê bao của một số đường truyền tin thay đổi. Tổng công ty muốn xác định
với chi phí mới thì đường truyền thứ k có là đường không tiềm năng hay không để
xem xét chấm dứt việc thuê đường truyền này.
Yêu cầu: Cho Q
giả định, mỗi giả định cho biết danh sách các đường truyền tin với chi phí thuê
mới và chỉ số k. Với mỗi giả định về chi phí mới thuê đường truyền tin, hãy xác
định đường truyền tin thứ k có là đường truyền tin không tiềm năng trong mạng
không.
Dữ liệu
vào: từ tệp văn bản COMNET.INP
+ Dòng đầu là T – số testcase. T nhóm dòng, mỗi nhóm cho
thông tin về một testcase.
+ Dòng
thứ nhất gồm 3 số nguyên dương N, M, Q (Q <= 30).
+ Dòng
thứ i trong M dòng tiếp theo chứa 3 số nguyên dương ui, vi,
wi (ui ≠ vi, wi <
109).
+ Dòng thứ j trong Q dòng tiếp theo mô tả giả
định thứ j:
- Số đầu tiên là chỉ số kj của
đường truyền tin cần xem xét
- Tiếp
theo là sj ( sj <= 100) cho biết số lượng
đường truyền có chi phí thuê mới
- Cuối
cùng là sj cặp số nguyên dương tp, cp cho
biết đường truyền thứ tp có chi phí thuê mới là cp (cp <
109).
Dữ liệu ra: ghi vào tệp văn bản COMNET.OUT
+ Gồm T nhóm dòng, mỗi nhóm
gồm Q dòng. Mỗi dòng là câu trả lời cho giả định tương ứng trong input. Ghi YES
nếu câu trả lời là khẳng định và NO trong trường hợp ngược lại.
Ví dụ:
COMNET.INP
|
COMNET.OUT
|
1
3 3 2
1 2 1
1 3 2
2 3 3
3 2 2 4 3 4
1 1 1 4
|
NO
YES
|
Giới hạn
+ 30% số test đầu có 1 ≤ N ≤ 100;
+ 30% số test tiếp theo có 1 ≤ N ≤ 104 và 1 ≤ M ≤
105;
+ 40% số test còn lại có 1 ≤ N ≤ 105 và 1 ≤ M ≤ 106.
