คำอธิบายวิธีทำพร้อม code สำหรับข้อ toi20_route

สรุปโจทย์

ในมหาวิทยาลัยศิลปากร มีสถานที่สำคัญทั้งหมด $N$ จุด และมีรถขนส่งไฟฟ้าทั้งหมด $M$ คัน โดยรถขนส่งไฟฟ้าแต่ละคัน จะรับ-ส่งผู้โดยสารระหว่างสถานที่สำคัญ 2 จุดเท่านั้น และ รถหมายเลข $i$ จะมีค่าใช้จ่ายเฉพาะคันคือ $w[i]$ สำหรับทุกๆ $1 \leq i \leq M$

นายสมหวังผู้ได้รับมอบหมายให้จัดรถขนส่งไฟฟ้า ได้พบว่า หากเราทราบว่ารถคันไหนวิ่งระหว่างจุดไหน เราสามารถคำนวณ “การจัดสรรแบบประหยัด” ได้ ซึ่งการจัดสรรแบบประหยัดนั้น คือ การเลือกรถ $N - 1$ คันจากเส้นทางที่กำหนดให้ เพื่อให้ค่าใช้จ่ายรวมของรถที่เลือกมีค่าน้อยที่สุด และผู้ใช้บริการจะต้องสามารถเดินทางไป-มาระหว่างจุดทั้ง $N$ จุดได้

สิ่งที่ต้องทำ

เขียนโค้ดที่จะหาวิธีการจัดรถขนส่งไฟฟ้า ที่จะทำให้ “การจัดสรรแบบประหยัด” มีค่ามากที่สุด

ขอบเขตข้อมูล

$2 \leq N \leq 300,000$
$N - 1 \leq M \leq min(1,000,000  , \frac{N(N - 1)}{2})$

Prerequisites

• Minimum Spanning Tree (จริงๆไม่จำเป็นหรอก แต่ถ้ารู้จักก็จะเข้าใจคำอธิบายเฉลยของโจทย์ข้อนี้ได้ง่ายยิ่งขึ้น)

ข้อสังเกต

“การจัดสรรแบบประหยัด” มันก็คือการหา Minimum Spanning Tree นั่นแหละ

วิธีทำ

เนื่องจาก MST นั้น จะพยายามเลือก edge ที่มี weight น้อยๆ เราก็จะต้องบังคับให้เขาเลือก edge ที่มี weight มากๆ โดยที่เราจะพยายามทำให้กราฟส่วนที่มี weight น้อยๆให้มี edge เยอะๆ และจะพยายามทำให้กราฟส่วนที่มี weight มากๆให้มี edge น้อยๆ

ภาพที่ 1 ตัวอย่างกราฟดังที่กล่าวมาๆ

ทีนี้ เราก็แค่เขียนโค้ดที่จะทำตามนั้น ซึ่งเราก็แค่เขียนโดยใช้วิธีต่อไปนี้:

1. loop $i$ ตั้งแต่ $1$ ถึง $N$
   1.1. เชื่อม $i, i - 1$ เก็บไว้ใน $ans$ แล้วลดค่า $M$ ไป 1
   1.2. loop $j$ ตั้งแต่ $i - 2$ ถึง $1$
   • แต่ละรอบที่ loop เราจะเช็กว่า $M$ มีค่าเท่ากับ $N - i$ หรือไม่
     • ถ้าใช่ แสดงว่าเราจะต้องนำเส้นเชื่อมที่เหลือไปเชื่อม node ทั้งหมดตั้งแต่ $i$ ถึง $N$ เราก็จะเก็บค่า $i$ ไว้ในตัวแปร $curr$ เพื่อ mark ไว้ว่า node ล่าสุดที่เราเชื่อมไปคือ node ที่เท่าไหร่ เพื่อจะได้นำไปใช้ต่อในขั้นตอนที่ 2
     • ถ้าไม่ใช่ เราก็จะเชื่อม $i$ กับ $j$ เก็บไว้ใน $ans$ แล้วลดค่า $M$ ไป 1
2. loop $i$ ตั้งแต่ $curr$ ถึง $N - 1$ แล้วเชื่อม $i, i + 1$ เก็บไว้ใน $ans$

เมื่อเสร็จแล้ว ก็ return $ans[]$ ได้เลย

Summary

• ใช้หลักการทำงานของ MST มาเลือกว่า จะให้ edge ไหน มี weight เท่าไหร่

Solution Code:

#include <bits/stdc++.h> 

using namespace std; 

vector <pair <int, int>> route(int n, vector <int> w) { 
	int m = w.size(); 
	vector <pair <int, int>> ans; 
	bool cant = false; 
	int curr = 1; 
	if (m == n && n >= 3) ans.emplace_back(1, 3); 
	if (m > n) { 
		for (int i = 2; i <= n; i++) { 
			ans.emplace_back(i, i - 1); m--; 
			for (int j = i - 2; j > 0; j--) { 
				if (m == n - i) { 
					cant = true; 
					break; 
				} 
				m--; 
				ans.emplace_back(i, j); 
			} 
			if (cant) { 
				curr = i; 
				break; 
			} 
		} 
	} 
	for (auto &[x, y] : ans) if (x > y) swap(x, y); 
	for (int i = curr; i < n; i++) ans.emplace_back(i, i + 1); 
	return ans; 
}

Total Time Complexity: $O(M)$

หากมีข้อสงสัย comment ไว้ใต้ post ได้เลยนะครับ 🙇‍♂️🙇‍♂️
ศึกษาโจทย์เพิ่มเติมได้ที่ Fast X Fourier