POJ 3680 Intervals：最大費用流選擇區間

題目大意

給 n 個開區間 (aᵢ, bᵢ) 及權值 wᵢ。選若干區間，使任意點被覆蓋次數 ≤ k。最大化總權值。n ≤ 10000, k ≤ 10000, 坐標 ≤ 10⁶。

建模：最大費用流

• 將所有端點離散化排序，得到有序坐標 x₀ < x₁ < ... < xₘ。
• 構建圖：
  - 源點 S = m，匯點 T = m+1。
  - 相鄰坐標間加邊：`i → i+1` 容量 k、費用 0；`i+1 → i` 容量 INF、費用 0（保證流向單向）。
  - 每個區間 (aᵢ, bᵢ) 加邊：`id(aᵢ) → id(bᵢ)` 容量 1、費用 wᵢ（選擇該區間獲得權值）。
• 從 S 向 T 流 k 單位流（對應 k 條「軌道」），最大費用即答案。

關鍵代碼結構

// 最小費用流模板改最大費用：SPFA 找最大增廣路 (dist 用 -inf 初始化，放鬆條件 dist[v] < dist[u] + cost)
// 或直接將費用取負跑最小費用流
struct Edge { int to, cap, cost, rev; };
vector G[MAXV];
void addEdge(int u, int v, int cap, int cost) {
    G[u].push_back({v, cap, cost, (int)G[v].size()});
    G[v].push_back({u, 0, -cost, (int)G[u].size()-1});
}
// SPFA 求最大費用增廣路
bool spfa(int s, int t, int& flow, int& cost) { ... }

複雜度

• 節點數 ≤ 2n+2 ≈ 20000，邊數 ≈ 3n。
• 流量 k ≤ 10000。SPFA 最大費用流實測極快（圖為 DAG 且無負環）。

總結

POJ 3680 是「區間選擇 + 覆蓋限制」建模為**最大費用流**的經典題。關鍵步驟：
1. 端點離散化。
2. 相鄰點連邊限制覆蓋數。
3. 區間連邊獲取權值。
4. 跑 k 流量最大費用流。
掌握此建模範式，可解決所有「資源分配 + 區間衝突」類優化問題。