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.|

MATCH2 - Bộ ghép đầy đủ trọng số cực tiểu

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/match2


Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, ..., xn, các đỉnh của Y ký hiệu là y1, y2, ..., yn. Mỗi cạnh của G được gán một trọng số không âm. Một bộ ghép đầy đủ trên G là một tập n cạnh thuộc E đôi một không có đỉnh chung. Trọng số của bộ ghép là tổng trọng số các cạnh nằm trong bộ ghép.

Ràng buộc: Luôn tồn tại ít nhất một bộ ghép đầy đủ trên G.
Chú ý dùng Eof chứ không dùng SeekEof

Input

• Dòng 1: Chứa số n (1 ≤ n ≤ 200)
• Các dòng tiếp theo, mỗi dòng chứa 3 số nguyên i, j, c cho biết có một cạnh (xi, yj) và trọng số cạnh đó là c (0 ≤ c ≤ 200).

Output

• Dòng 1: Ghi trọng số bộ ghép tìm được
• n dòng tiếp, mỗi dòng ghi hai số (u, v) tượng trưng cho một cạnh (xu, yv) được chọn vào bộ ghép.

Example

Input:
4
1 1 0
1 2 0
2 1 0
2 4 2
3 2 1
3 3 0
4 3 0
4 4 9


Output:
3
1 1
2 4
3 2
4 3


Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-02-26
Thời gian chạy: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 VB.NET
Nguồn bài:Sách DSAP của thầy Lê Minh Hoàng , giáo viên khối chuyên Sư Phạm

hide comments
2021-05-27 18:02:11
Tham khảo: https://vnspoj.github.io/problems/MATCH2
2020-10-27 03:59:02
ez
2018-10-17 05:59:23
1 Hit
frostpixel aka.How 2 AC
2017-08-21 08:56:07 Ðặng Minh Tiến
https://kienthuc24h.com/hungari-cap-ghep-cuc-dai-co-trong-so-cuc-tieu/
2016-12-08 04:40:54 le tuan dung
Tôi là Lê Tuấn Dũng. Xin chào các fan hâm mộ.
2016-11-22 09:44:29
Tuyên bố đã accepted bằng Java <(")
2015-09-08 14:12:02
https://thewizard6296.wordpress.com/2015/09/04/5/
2015-04-02 17:39:16 Dương Bảo


Last edit: 2015-04-02 17:39:52
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.