Đảo Tham Lam

[quangtq]

Trên đường đi tìm Cha, Gon bị lạc đến đảo Tham Lam.
Hòn đảo rất kỳ quái, người dân ko dùng tiền mà dùng thẻ để trao đổi. Trên mỗi thẻ ghi 1 số nguyên nằm trong khoảng [1..N] và được gọi là mã số của thẻ. Chỉ có 1 cách duy nhất ra khỏi đảo là đem N thẻ có mã đôi 1 khác nhau đổi lấy vé tàu.
Gon có 2 cách kiếm thẻ:
_ Nhặt thẻ người khác đánh rơi
_ Trao đổi với ngân hàng: dùng 1 thẻ của mình đổi lấy 1 thẻ khác của ngân hàng. Lệ phí 1 lần đổi là 1 cục vàng (dùng đúc thẻ mới)
Rất may là Gon được 1 người tốt bụng tặng cho N thẻ nên chỉ còn phải ra ngân hàng đổi thẻ. Vì chuyến đi còn dài nên Gon phải tiết kiệm vàng. Giúp Gon tìm cách đổi tốn ít vàng nhất mà vẫn đổi được vé. Biết rằng luôn tồn tại ít nhất 1 cách đổi.
Input: file Greed.inp:
_ Dòng đầu chứa số n (n<=100)
_ Dòng 2 ghi N số nguyên là mã số của N thẻ Gon có
_ Tiếp theo là 1 số dòng, trên mỗi dòng chứa 2 số u, v có nghĩa là có thể đổi thẻ có mã số u của Gon lấy thẻ mã số v của bank và ngược lại.
Output: file Greed.out:
_ Dòng đầu ghi tổng số vàng ít nhất phải trả khi đổi thẻ.
_ Các dòng sau ghi theo dạng u -> v nghĩa là dùng thẻ mã số u đổi lấy thẻ mã số v
Các dữ liệu trên 1 dòng cách nhau ít nhất 1 dấu space.

Mọi người làm thử nhá

[bld]

đồ thị àh ? có phải vừa đọc xong mấy ông hungary rồi post đề ko, vậy phải để m nghiên cúư tí đã ;p

[quangtq]

đồ thị àh ? có phải vừa đọc xong mấy ông hungary rồi post đề ko, vậy phải để m nghiên cúư tí đã ;p
Uhm. Chuẩn đấy. Hungary bài này rất dễ.
Thử làm cách khác xem
P/S: Thứ 3 7h00 sáng mình xuống HN. :D. Lúc nào xuống nhớ find

[m2mpro]

Do đổi xong các tấm thẻ bắt buộc phải có trong khoảng [1..N] => cái nào đã trùng thì đổi thôi :)

[quangtq]

Chuẩn. Ý tưởng rất đúng. Không hề phức tạp.