NKNET - Mạng truyền tin
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Trong một chiến dịch, người ta thu thập được thông tin về một mạng truyền tin của đối phương, bao gồm n trạm và m đường nối giữa những trạm này. Các trạm được đánh số từ 1 đến n. Hai trạm liên lạc được với nhau nếu có một đường nối trực tiếp giữa chúng hoặc có một dãy những đường nối đi qua một số trạm trung gian nào đấy.
Yêu cầu đặt ra là tìm cách phá hủy một số đường nối để hai trạm cho trước không liên lạc được với nhau. Giả thiết ban chỉ huy đủ nhân lực để cử mỗi đội phụ trách việc phá huỷ một đường nối và lệnh phá huỷ được phát đồng thời. Do địa hình khác nhau nên việc phá huỷ mỗi đường nối cần một khoảng thời gian tương ứng khác nhau. Hãy tìm một phương án để thời điểm hoàn thành nhiệm vụ là sớm nhất. Nếu có nhiều phương án như thế, hãy tìm phương án phải cử ít đội nhất.
Dữ liệu
- Dòng đầu ghi giá trị n là số trạm của mạng (không quá 100).
- Dòng tiếp ghi giá trị m là số đường nối của mạng (không quá n(n-1)/2).
- m dòng tiếp theo, mỗi dòng ghi thông tin của một đường nối gồm 3 giá trị nguyên dương: hai giá trị đầu là số hiệu của ha trạm xác định đường nối, giá trị sau (không quá 100) là thời gian cần thiết cho việc phá hủy đường nối này.
- Dòng cuối cùng ghi hai giá trị là số hiệu của hai trạm cần cắt đứt liên lạc.
Kết quả
- Dòng đầu ghi giá trị m là số đường nối cần phá hủy.
- m dòng tiếp theo, mỗi dòng mô tả một đường nối cần phá hủy gồm hai giá trị là số hiệu của hai trạm xác định đường nối này.
Các giá trị số ghi trên cùng một dòng cách nhau ít nhất một dấu trắng. Dữ liệu vào luôn đảm bảo có đường truyền tin nối hai trạm cần cắt liên lạc.
Ví dụ
Dữ liệu: 5 6 1 2 3 1 5 1 2 3 1 2 5 1 3 4 4 3 5 3 1 4 Kết qủa 3 1 5 2 3 2 5
Giải thích: thời gian hoàn thành nhiệm vụ là 1.
- Người up: paulmcvn