สำหรับโจทย์ข้อนี้ เราได้รับกราฟแบบระบุน้ำหนัก ไม่ระบุทิศทาง ที่ประกอบไปด้วย $N$ node และ $M$ edge

โจทย์ต้องการให้เลือกเส้นทางจาก node เริ่มต้น $s$ ไปยัง node ปลายทาง $d$ ที่ทำให้เราสามารถส่งนักท่องเที่ยวทั้งหมด $p$ คนขึ้นไปได้โดยแบ่งกลุ่มให้ได้จำนวนกลุ่มน้อยที่สุด การส่งนักท่องเที่ยวมีเงื่อนไขคือ

• จะส่งคนขึ้นไปได้ไม่เกิน edge ที่รับน้ำหนักได้น้อยที่สุดในเส้นทาง
• ทุกกลุ่มจะต้องมีมัคคุเทศก์ 1 คนเสมอ

เช่น หากมีนักท่องเที่ยว 99 คนแล้ว edge รับน้ำหนักได้ไม่เกิน 25 จะต้องใช้ทั้งหมด 5 กลุ่ม โดย 4 กลุ่มแรกประกอบด้วยมัคคุเทศก์ 1 คนต่อนักท่องเที่ยว 24 คน และกลุ่มสุดท้ายมีมัคคุเทศก์ 1 คนกับนักท่องเที่ยว 3 คน

เพื่อให้แบ่งกลุ่มได้จำนวนกลุ่มน้อยที่สุด เราควรเลือกเส้นทางที่ edge ที่รับน้ำหนักได้น้อยที่สุด รับน้ำหนักได้มากสุดเท่าที่เป็นไปได้

เราสามารถใช้ Kruskal's algorithm และ Union-find disjoint set มาดัดแปลงหา Maximum spanning tree โดย sort edge list ตาม weight จากมากไปน้อย แล้วเพิ่มแต่ละ edge เข้าไปในกราฟจนกว่า $s$ และ $d$ จะอยู่ใน component เดียวกัน

เมื่อ $s$ และ $d$ อยู่ใน component เดียวกันแล้ว จะได้ว่า edge ที่เพิ่งเพิ่มไปล่าสุดคือน้ำหนักมากสุดที่เส้นทางนี้รับได้ สมมุติว่าเท่ากับ $w$

เนื่องจากแต่ละกลุ่ม จำเป็นต้องเหลือที่ไว้ให้มัคคุเทศก์ 1 คนเสมอ เพราะฉะนั้นจะเปรียบเสมือนว่าเส้นทางนี้สามารถรับนักท่องเที่ยวได้ไม่เกินครั้งละ $p-1$ คน ดังนั้น จึงต้องส่งนักท่องเที่ยวทั้งหมด $\frac{p}{w-1}$ ครั้ง (ปัดขึ้น)

Time Complexity คือ $O(N + M \log M)$ เพราะเราจำเป็นต้อง sort edge list ซึ่งมีทั้งหมด $M$ เส้น

Space Complexity คือ $O(N+M)$ (ไม่จำเป็นต้องเก็บข้อมูลเพิ่มเติมนอกจาก Union-find disjoint set)