2005 : Training
Problem type : Batch
Time limit : 0.3 second(s)
Memory limit : 64 megabyte(s)
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 หน่วย
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
มีเมืองอยู่ 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 สมาชิก (0 บอท)