เราสามารถมองสิ่งที่โจทย์กำหนดมาให้เป็น flow network ได้ดังนี้

• ปลายแต่ละด้านของแท่งไม้แต่ละแท่ง เป็น node
• แท่งไม้ที่รับน้ำหนักมดได้ $w$ ขบวน จะเป็น edge ที่เชื่อม node ที่อยู่ปลายแท่งไม้ทั้งสองข้าง และมี capacity เป็น $w$
• พิกัด $(0,0)$ เป็น source (หรือ $s$) และมี edge ที่มี capacity เป็น $\infty$ เชื่อมไปยังทุกโหนดที่มีพิกัดแกน $x$ เป็น $0$
• ในทำนองเดียวกัน พิกัด $(L,0)$ เป็น sink (หรือ $t$) และมี edge ที่มี capacity เป็น $\infty$ เชื่อมไปยังทุกโหนดที่มีพิกัดแกน $x$ เป็น $L$

ชุดทดสอบตัวอย่างที่ 1 สามารถมองเป็น flow network ได้เช่นดังรูป

(อนึ่ง เส้นตรงสีน้ำตาล คือเส้นริมฝั่งของแม่น้ำ ซึ่งจะถูกกล่าวถึงช่วงต่อไป)

จะได้ว่า แท้จริงแล้ว โจทย์ข้อนี้คือ Maximum flow problem นั่นเอง

สำหรับข้อนี้ หากใช้ Algorithm สำหรับคำนวณ Maximum flow โดยตรงจะใช้เวลามากเกินไป

Observation

สังเกตได้ว่าตัวกราฟของ flow network นั้นเป็น planar graph และนอกจากนี้ ยังเป็นกราฟบนระนาบสองมิติ เราสามารถ model กราฟขึ้นมาใหม่จากกราฟเดิม ให้สามารถคำนวณ Minimum cut อย่างมีประสิทธิภาพได้ โดยการแปลงปัญหานี้ให้เป็น Shortest Path problem แทน

(เนื่องจาก Maximum flow = Minimum cut เสมอโดย Max-flow Min-cut theorem เราจึงสามารถคำนวณ Minimum cut แทนได้)

Graph Modeling

ต่อจากนี้ เราจะไม่สนใจ edge ระหว่าง

• โหนด $(0,0)$ กับโหนดที่มีพิกัดแกน $x$ เป็น $0$ และ
• โหนด $(L,0)$ กับโหนดที่มีพิกัดแกน $x$ เป็น $L$

เพราะการลากเส้น Cut ผ่าน edge เหล่านี้จะเป็นการเพิ่มค่าของ Cut อย่างใช่เหตุ เนื่องจากไม่จำเป็นต้องลากเส้นผ่าน edge เหล่านี้เลย ภาพต่อไปนี้คือชุดทดสอบตัวอย่างที่ $1$ เมื่อทำการนำ edge ดังกล่าวออกแล้ว

นิยาม เราจะนิยามให้ "Region" หมายถึง พื้นที่ในกราฟที่ถูกล้อมด้วย edge หรือเส้นริมฝั่งแม่น้ำ

นิยาม เราจะนิยามให้ "Start Region" หมายถึง Region ที่อยู่ข้างบนสุด

นิยาม เราจะนิยามให้ "End Region" หมายถึง Region ที่อยู่ข้างล่างสุด

ดังในรูปของชุดทดสอบตัวอย่างที่ 1 กราฟจะมีทั้งหมด $5$ Region (แต่ละ Region จะมีหมายเลขกำกับไว้)

จากรูป,

• Start Region คือ $[1]$ และ End Region คือ $[5]$
• สังเกตุได้ว่า Cut คือ การลากเส้นจาก Start Region ไปยัง End Region โดยค่าของ Cut คือผลรวมน้ำหนักของ edge ที่ลากผ่าน
• $(a)$, $(b)$, $(c)$ คือตัวอย่างของ Cut ที่เป็นไปได้ แต่ $(a)$ เป็น Cut ที่มีผลรวมน้ำหนักของ edge เป็น $2$ ซึ่งน้อยที่สุดเท่าที่เป็นไปได้แล้ว ในขณะที่ $(b)$ และ $(c)$ มีผลรวมน้ำหนักเป็น $3$

เราสามารถแปลงเป็นปัญหา Shortest Path โดยการมองว่า

• แต่ละ Region เป็นเสมือน node ๆ หนึ่ง
• เส้นที่คั่นระหว่างสอง Region จะเป็น edge เชื่อมคู่ node ของทั้งสอง Region นั้น
• เราต้องการเดินจาก node ของ Start Region ไปยังโหนดของ End Region โดยให้ผลรวมของน้ำหนักเส้นน้อยที่สุด

กราฟของชุดทดสอบตัวอย่างที่ $1$ จึงสามารถ model เป็นกราฟของปัญหา Single-Source Shortest Path ได้ดังรูป

สามารถเห็นได้ว่า Shortest Path จาก $[1]$ ไปยัง $[5]$ ก็คือ Minimum Cut นั่นเอง

Algorithm

ความท้าทายของโจทย์ข้อนี้คือการคิดและ implement วิธีสร้างกราฟขึ้นมาเพื่อนำมาใช้แก้ปัญหา Shortest Path

ก่อนอื่น จากเงื่อนไขของโจทย์ ชุดทดสอบสามารถมี "component ลอย" ได้ กล่าวคือ เป็นกลุ่มของกิ่งไม้ที่ลอยอยู่บนแม่น้ำเฉย ๆ ไม่มีส่วนใดเชื่อมต่อกับริมฝั่งแม่น้ำเลย ดังเช่นกิ่งไม้ที่เชื่อมต่อ $(1,3)$ กับ $(1,4)$ ในกรณีของรูปดังต่อไปนี้

เราจะไม่สนใจ "component ลอย" ภายในกราฟ เพราะอย่างไร เราก็สามารถลากเส้นอ้อมหลบ component เหล่านี้ได้เสมอ การลากเส้นผ่านกิ่งไม้เหล่านี้จะเป็นการเพิ่มน้ำหนักรวมของ cut โดยไม่จำเป็น

ย้อนกลับมายังกราฟเริ่มต้นของชุดทดสอบตัวอย่างที่ 1

• สร้าง "โหนดสมมุติ" ขึ้นมา 4 โหนด รอบสี่ทิศแนวทะแยงของแต่ละ node ดังรูป
  
• สร้างเส้นเชื่อมระหว่างโหนดสมมุติภายใน node ที่อยู่ในแนวตั้งหรือแนวนอนเดียวกัน
  
• หากเป็น edge ที่มีปลายหนึ่ง (หรือทั้งสอง) เป็นโหนดสมมุติที่อยู่บนฝั่ง(กล่าวคือไม่ได้อยู่ในแม่น้ำ) ให้มีน้ำหนักเป็น $\infty$
• หากเป็น edge ที่ตัดกับเส้นเชื่อมในกราฟตั้งต้น ให้มีน้ำหนักเท่ากับเส้นเชื่อมนั้น
• หากเป็น edge ที่ไม่ได้ตัดกับเส้นเชื่อมในกราฟตั้งต้น ให้มีน้ำหนักเป็น $0$
  
• สำหรับคู่ node ที่มี edge เชื่อมในกราฟตั้งต้น ให้สร้างเส้นเชื่อมน้ำหนัก $0$ เชื่อมสองคู่โหนดสมมุติที่อยู่ใกล้กันในแนว edge ดังกล่าว
  
• ท้ายที่สุด สร้าง edge น้ำหนัก $0$ เชื่อมระหว่างโหนดสมมุติของ node ที่มีพิกัดในแนวแกน $x$ เป็น $0$ ที่อยู่ติดกันในแนวตั้ง (ดังรูปด้านล่าง)
• ในทำนองเดียวกัน สร้าง edge น้ำหนัก $0$ เชื่อมระหว่างโหนดสมมุติของ node ที่มีพิกัดในแนวแกน $x$ เป็น $L$ ที่อยู่ติดกันในแนวตั้ง
  

จากกราฟที่เรา model ขึ้นมา สามารถสังเกตได้ว่า

• การเดินทางระหว่างโหนดสมมุติใน Region เดียวกัน จะไม่ได้รับน้ำหนักรวมเพิ่ม
• การเดินทางระหว่างโหนดสมมุติที่อยู่ต่าง Region กัน น้ำหนักรวมจะเพิ่มขึ้นตามน้ำหนักของ edge ที่เราก้าวข้าม

ในที่สุด เราสามารถใช้ Dijkstra's Algorithm บนกราฟนี้ โดยให้โหนดสมมุติทั้งหมดที่อยู่ใน Start Region เป็นจุดเริ่มต้น ค่า shortest path ที่เราได้จากโหนดสมมุติใน End Region จะเป็นค่า Minimum Cut ซึ่งก็คือคำตอบของปัญหาของเรานั่นเอง

อย่างไรก็ดี เราไม่จำเป็นต้องใช้โหนดสมมุติใน Start Region ทุกโหนดเป็นจุดเริ่มต้นก็ได้ เลือกใช้โหนดใดโหนดหนึ่งก็เพียงพอ เพราะการเดินทางระหว่างโหนดสมมุติภายใน region ข้างบนสุดย่อมไม่ได้น้ำหนักเพิ่มอยู่แล้ว

ด้วยข้อจำกัดของการ model กราฟของเรา การเลือกใช้โหนดสมมุติจาก "component ลอย" ใน Start Region อาจจะทำให้เราไม่สามารถหาเส้นทางไปถึงโหนดสมมุติใน End Region ได้ เช่น ในภาพตัวอย่างนี้ หากเลือกโหนด $(1,3)$ หรือ $(1,4)$ เป็นจุดเริ่มต้น จะไม่สามารถไปถึง End Region ได้เพราะไม่มี edge เชื่อมลงไปข้างล่าง

Overall Time Complexity : $\mathcal{O}(M \log M)$

Space Complexity : $\mathcal{O}(M)$