2005 : Training
Problem type : Batch
Time limit : 0.3 second(s)
Memory limit : 64 megabyte(s)
ในระหว่างการฝึกซ้อม คนที่ขี่ตามจะได้เปรียบเพราะคนที่นำหน้าจะช่วยบังลมให้ และทั้งคู่จะสลับกันนำหน้าเมื่อไปถึงแต่ละเมือง เพื่อที่จะให้ทั้งคู่ไม่ได้เปรียบหรือเสียเปรียบต่อกันทั้งคู่จึงเลือกที่จะฝึกซ้อมในเส้นทางที่มีจำนวนถนนเป็นเลขคู่เมอโก (Mirko) และ สลาฟโก (Slavko) กำลังอยู่ในระหว่างการฝึกซ้อมเพื่อการแข่งขันจักรยานทางไกลประจำปีซึ่งจัดขึ้นที่ ประเทศโครเอเชีย เพื่อชัยชนะจำเป็นต้องมีเส้นทาง (route) สำหรับฝึกซ้อม

มีเมืองอยู่ N เมือง และมีถนนอยู่ M สายในประเทศนี้ ถนนทุกเส้นจะเป็นการเชื่อมต่อกันระหว่างเมืองและสามารถเดินทางในทิศทางใดก็ได้ ถนนที่มีการราดยาง (paved) มีทั้งหมด N-1 สาย และถนนสายอื่นๆจะเป็นถนนที่ไม่ได้ราดยาง โชคดีที่การออกแบบการเชื่อมโยงของถนนทำมาเป็นอย่างดี ทำให้ทุกคู่ของเมืองเชื่อมต่อกันด้วยถนนที่ราดยางแล้ว หรือพูดภาษานักคอมพิวเตอร์ก็คือว่า เมือง N เมือง และ ถนนราดยาง N-1 สายนี้เชื่อมต่อกันเป็นโครงสร้างต้นไม้ นอกจากนี้ ในแต่ละเมืองจะมีถนนเชื่อมอยู่ทั้งหมดอย่างมากที่สุดรวม 10 สาย

เส้นทางการซ้อมจะเริ่มจากเมืองหนึ่งผ่านไปตามถนนหลายๆเส้นและกลับมาสิ้นสุดที่เมืองที่เริ่มต้น ทั้งเมอโกและสลาฟโกชอบที่จะไปที่ใหม่เสมอ ดังนั้นทั้งคู่จะไม่เข้าเมืองใดๆ หรือใช้ถนนใดๆ ซ้ำ ทั้งนี้การเริ่มต้นจะเริ่มที่เมืองใดก็ได้และไม่จำเป็นต้องไปทุกเมือง

ในระหว่างการฝึกซ้อม คนที่ขี่ตามจะได้เปรียบเพราะคนที่นำหน้าจะช่วยบังลมให้ และทั้งคู่จะสลับกันนำหน้าเมื่อไปถึงแต่ละเมือง เพื่อที่จะให้ทั้งคู่ไม่ได้เปรียบหรือเสียเปรียบต่อกันทั้งคู่จึงเลือกที่จะฝึกซ้อมในเส้นทางที่มีจำนวนถนนเป็นเลขคู่

คู่แข่งของเมอโกและสลาฟโกคิดขัดขวางการฝึกซ้อมจึงตัดสินใจปิด (block) ถนนที่ไม่ได้ราดยางบางเส้นเพื่อที่ทำให้เมอโกและสลาฟโกไม่สามารถหาเส้นทางที่มีเงื่อนไขตามความต้องการข้างต้น การปิดถนนที่ไม่ราดยางแต่ละเส้นมีค่าใช้จ่าย (cost) ของการปิดถนนซึ่งเป็นจำนวนเต็มบวก อย่างไรก็ตามไม่มีใครสามารถปิดถนนราดยางได้

โจทย์
โจทย์จะกำหนดรายละเอียดของการเชื่อมต่อของถนนระหว่างเมืองมาให้ จงเขียนโปรแกรมเพื่อหา ค่าใช้จ่ายรวมที่ต่ำที่สุด (smallest total cost) ในการปิดถนนที่ทำให้ไม่มีเส้นทางการฝึกซ้อมที่เป็นไปตามเงื่อนไขที่โจทย์กำหนดข้างต้นได้

ข้อมูลนำเข้า
บรรทัดแรก มีจำนวนเต็ม 2 ค่าคือจำนวนเมืองทั้งหมด N และจำนวนถนนทั้งหมด M โดยที่ 2 ≤ N ≤ 1 000,
N-1 ≤ M ≤ 5 000
ต่อจากนั้น M บรรทัด แต่ละบรรทัดเป็นรายละเอียดของถนนแต่ละเส้น ซึ่งประกอบด้วยจำนวนเต็มสามค่า คือ A B และ C โดยที่ 1 ≤ A ≤ N, 1 ≤ B ≤ N, 0 ≤ C ≤ 10 000 ทั้งนี้ A และ B คือหมายเลขของเมือง ซึ่งย่อมต้องมีค่าที่ต่างกัน แสดงว่ามีถนนเชื่อมต่อโดยตรงระหว่างเมืองทั้งสอง ถ้า C=0 หมายความว่า ถนนเส้นนี้เป็นถนนราดยาง และ ถ้า C>0 นั่นคือถนนเส้นนี้ไม่ได้ราดยางและค่า C ก็คือค่าใช้จ่ายในการปิดถนนนั่นเอง

ข้อมูลส่งออก

ข้อมูลส่งออกจะต้องมีจำนวนเต็มเพียงค่าเดียว ซึ่งเป็นค่าใช้จ่ายที่ต่ำที่สุด ตามรายละเอียดของโจทย์ข้างต้น
การให้คะแนน

ที่มา: International Olympiad in Informatics 2007 DAY 2
ZAGREB – CROATIA AUGUST 15 – 22

คำอธิบายตัวอย่างข้อมูลนำเข้า และข้อมูลส่งออก ชุดที่ 1



ลักษณะการเชื่อมต่อของถนนในตัวอย่างที่หนึ่ง ถนนราดยางแสดงเป็นเส้นหนา



มีเส้นทางที่เป็นไปได้ทั้งหมด 5 เส้นทางสำหรับเมอโกและสลาฟโก ถ้าถนน 1-3, 3-5, และ 2-5 ถูกปิด เมอโกและสลาฟโก จะไม่สามารถใช้เส้นทางใดได้ ค่าใช้จ่ายทั้งหมดในการปิดถนนคือ 5
เป็นไปได้ที่จะปิดถนนแค่สองเส้น คือ 2-4 และ 2-5 แต่นี่จะใช้ค่าใช้จ่ายมากกว่า คือ 6 หน่วย

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1
5
9 14
1 2 0
1 3 0
2 3 14
2 6 15
3 4 0
3 5 0
3 6 12
3 7 13
4 6 10
5 6 0
5 7 0
5 8 0
6 9 11
8 9 0
48

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 20 ผู้เยี่ยมชมและ 0 สมาชิก (3 บอท)