Tin học Bài toán "Đảo Tham Lam"

[ttd190902]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Biên soạn: Trần Minh Quân - Chuyên Tin học khóa 2000 - 2003
Trên đường đi tìm cha thì cậu bé Gon bị lạc đến đảo Tham Lam. Hòn đảo này rất kì quái, người dân không dùng không dùng tiền mà dùng thẻ để trao đổi. Trên mỗi thẻ ghi một số nguyên nằm trong khoảng [1,N], và được gọi là mã số của thẻ. Chỉ có một cách duy nhất để ra khỏi đảo là đem N thẻ có mã số đôi một khác nhau (tức là có mã số 1, 2, 3,..., N) đổi lấy vé tàu.
Gon có 2 cách để kiếm thẻ ở trên đảo:

• Nhặt thẻ mà người khác đánh rơi.
• Trao đổi với ngân hàng của đảo: dùng 1 thẻ của mình đổi lấy một thẻ khác của ngân hàng, lệ phí 1 lần đổi là 1 cục vàng.

Rất may, Gon được một 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. Bạn hãy giúp Gon, lập trình tìm cách đổi để tốn ít vàng nhất mà vẫn đổi được vé tàu ra khỏi đảo. Biết rằng luôn tồn tại ít nhất một cách đổi.

Dữ liệu vào: vào từ file văn bản GREED.inp:

• Dòng thứ nhất: số nguyên N (N <= 100).
  
• Dòng thứ hai: ghi N số nguyên là mã số của N thẻ mà Gon có.
• Tiếp theo là một số dòng, trên mỗi dòng chứ 2 số u, v có nghĩa là có thể đổi thẻ có mã số u của Gon lấy thẻ có mã số v của ngân hàng và ngược lại.

Dữ liệu ra: ghi vào file văn bản GREED.out:

• Ghi tổng số vàng ít nhất phải trả cho ngân hàng để đổi thẻ.

Chú ý: Các dữ liệu số trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách.​

GREED.inp	GREED.out
4 1 1 1 1 1 2 2 3 1 4 3 4	4

[TBODY] [/TBODY]

Giải thích: 1->2: 1 cục vàng; 1->2->3: 2 cục vàng; 1->4: 1 cục vàng => 4 cục vàng

Bài toán này có thuật toán là xây dựng đồ thị 2 phía với 2 tập đỉnh là X và Y rồi tìm cặp ghép trọng số cực tiểu trên đồ thị này. Mình thấy hơi khó hiểu, không biết các bạn có cách giải khác dễ hiểu hơn không? Thanks

​