Custom Min Spanning Tree
1.0.0
การสร้างต้นไม้ที่ครอบคลุมจากข้อมูลอินพุตควรปฏิบัติตามกฎพื้นฐานทั้งสามนี้:
ภาพที่ 1. แผนการของการเชื่อมต่อที่เป็นไปได้ระหว่างโหนดกราฟ การเชื่อมต่อที่เป็นไปได้จะถูกอธิบายว่าเป็นขอบ การเชื่อมต่อที่อาจก่อให้เกิดต้นไม้ที่มีความต้องการจะถูกเน้นด้วยสีแดง กรณี a), b), c) สอดคล้องกับตัวอย่างที่ 1, 2, 3 ด้านล่าง ในบางกรณี (เช่นในกรณี B และ C) ต้นไม้ที่ทอดมากกว่าหนึ่งต้นอาจตอบสนองความต้องการของปัญหา อย่างไรก็ตามต้นไม้ที่ทอดทั้งหมดนั้นมีความยาวรวมเท่ากัน กรณี a) แสดงให้เห็นถึงความสำคัญของกฎข้อ 3 มีต้นไม้ที่มีขอบที่มีขอบ (1, 5) และ (5, 4) ซึ่งเป็นไปตามกฎข้อ 2 แต่ไม่เป็นไปตามกฎข้อ 3 เนื่องจากความยาวทั้งหมดของพวกเขาอย่างน้อย 17
รายการการเชื่อมต่อที่เป็นไปได้ทั้งหมดระหว่างโหนดและความยาวการเชื่อมต่อที่เกี่ยวข้องจะได้รับ คำนวณความยาวทั้งหมดของต้นไม้ที่ทอดซึ่งเป็นไปตามกฎทั้งสามที่แสดงในคำอธิบาย
ชุดข้อมูลสำหรับงานถูกสร้างขึ้นโดยครูของมหาวิทยาลัยเทคนิคเช็กสำหรับเรื่อง 'อัลกอริทึมขั้นสูง'
บรรทัดแรกของอินพุตประกอบด้วยสองจำนวนเต็ม N และ M คั่นด้วยพื้นที่ ค่า n คือจำนวนโหนด ค่า M คือจำนวนการเชื่อมต่อที่เป็นไปได้ระหว่างคู่ของโหนด ถัดไปมีบรรทัด M ซึ่งแต่ละบรรทัดแสดงถึงการเชื่อมต่อที่เป็นไปได้เดียว บรรทัดมีสามจำนวนเต็ม d1, d2, l คั่นด้วยพื้นที่ซึ่งหมายความว่าความยาวของการเชื่อมต่อที่เป็นไปได้ระหว่างโหนด D1 และ D2 เท่ากับ L. เครื่องตรวจจับมีหมายเลขตั้งแต่ 1 ถึง N การเชื่อมต่อที่เป็นไปได้จะแสดงอยู่ในลำดับแบบสุ่ม มันถือ n ≤ 30000 และ m ≤ 300000 ความยาวแต่ละความยาวมากที่สุด 10^9
เอาต์พุตเป็นหนึ่งบรรทัดที่มีความยาวรวมขั้นต่ำของเครือข่ายที่ต้องการ ผลลัพธ์ไม่เกิน 2^60
ตัวอย่างที่ 1 ข้อมูลอินพุตและเครือข่ายผลลัพธ์จะแสดงในภาพ 1 A)
ตัวอย่างที่ 2 ข้อมูลอินพุตและเครือข่ายผลลัพธ์จะแสดงในภาพ 1 B)
ตัวอย่างที่ 2 ข้อมูลอินพุตและเครือข่ายผลลัพธ์จะแสดงในภาพ 1 C)
งานถูกนำไปใช้ใน Java โดยใช้อัลกอริทึมการหายูเนี่ยนที่ได้รับการปรับปรุง (อธิบายที่นี่) ในอัลกอริทึมมีการใช้ HashMap รุ่นแก้ไขโดยผู้เขียน Justin Couch, Alex Chaffee และ Stephen Colebourne HashMap นี้ใช้เพียงจำนวนเต็มดั้งเดิมเท่านั้นและไม่ใช่วัตถุจำนวนเต็ม Java ซึ่งส่งผลให้ประสิทธิภาพดีขึ้น
