Một
hệ thống gồm N máy tính được nối thành một mạng có M kênh nối, mỗi kênh nối
hai máy tính trong mạng, giữa hai máy tính có không quá một kênh nối. Các máy
tính được đánh số từ 1 đến N, các kênh nối đánh số từ 1 đến M.
Việc truyền tin trực tiếp có thể thực hiện được đối với hai máy có kênh nối.
Các kênh nối trong mạng được chia thành ba loại 1, 2 và 3. Ta nói giữa hai máy
a và b trong mạng có đường truyền tin
loại k
(k=1 hoặc k=2) nếu tìm được dãy các máy (a=v1, v2,…,vp=b)
thoả mãn điều kiện: giữa hai máy vi và vi+1
hoặc có kênh nối loại k hoặc có kênh nối loại 3 (i=1, 2,..., p-1).
Yêu cầu: Cần tìm cách loại bỏ khỏi mạng một số nhiều nhất kênh nối nhưng
vẫn đảm bảo luôn tìm được cả đường truyền loại 1 lẫn đường truyền tin loại 2
giữa hai máy bất kỳ trong mạng.
Dữ liệu vào: từ tệp văn bản
RUTGON.INP như sau:
+ Dòng đầu tiên chứa hai
số N,
M (N≤500); M≤10000).
+ Dòng thứ i
trong M dòng tiếp theo chứa ba số nguyên dương u, v, s cho biết kênh thứ
i
nối hai máy u và v thuộc loại s.
Dữ liệu ra: ghi vào tệp văn bản
RUTGON.OUT gồm:
Dòng đầu tiên ghi số r
là số kênh cần loại bỏ.
+ Nếu r=-1 thì có nghĩa là trong mạng đã
cho tồn tại hai máy không có đường truyền loại 1 hoặc loại 2.
+ Nếu r=0
có nghĩa là mạng có đường truyền thoả mãn nhưng số kênh loại bỏ bằng 0.
+ Nếu r>0
thì r
dòng tiếp theo, mỗi dòng ghi chỉ số của một kênh cần loại bỏ.
Các số trên cùng một dòng của các tệp dữ liệu và tệp kết
quả cách nhau ít nhất một dấu cách.
Ví dụ:
RUTGON.INP
|
RUTGON.OUT
|
5 7
1 2 3
2 3 3
3 4 2
5 3 2
5 4 1
5 2 2
1 5 1
|
2
6
7
|
