Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKNET - Mạng truyền tin

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nknet


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.


Được gửi lên bởi:Jimmy
Ngày:2008-01-16
Thời gian chạy:0.100s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED

hide comments
2019-10-30 17:58:25
Chặt --->Tạo đồ thị mới ---> MinCut
2014-08-31 11:02:15 Hướng Thái Dương
luồng + chặt nhị phân :3
2014-07-15 12:37:48 ■■‡[ND] Bee Sociu■■‡
có lẽ là cây khung . lớn nhất hay nhỏ nhất gì đó :v
2012-07-28 02:00:31 KAKALOT
Sao lại phải phá nhiều thế nhỉ
2012-04-03 13:19:59 never give up
đúng là m,n nằm trên 1 dòng , hix
2011-06-22 08:12:12 T-7
Sặc, đề bảo n,m nằm trên 2 dòng vậy mà cho test thì n,m nằm trên cùng 1 dòng @.@ Làm hại WA cả chục lần
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.