POJ 3680 Intervals：費用流 + 離散化選區間最大權

建圖核心思想

將區間端點離散化排序得到點 1..tot。源點連最左點（容量 k，費用 0）。相鄰點連邊（容量 k，費用 0）表示「不選區間」。每個區間 [l, r] 連邊 l → r（容量 1，費用 -w）表示「選區間獲利 w」。最右點連匯點（容量 k，費用 0）。

為何正確

• 流量 k 限制任意位置最多 k 個重疊區間
• 增廣路徑對應 k 組不相交區間選擇
• 最小費用流對應最大權重和（費用取負）

關鍵代碼

// 離散化
sort(q+1, q+2*n+1);
fei[1] = q[1];
for (i=2; i<=2*n; i++) if (q[i]!=q[i-1]) fei[++tot]=q[i];

// 建圖
add(source, 1, k, 0);
for (i=1; i<=n; i++) {
    int l = get(a[i], tot), r = get(b[i], tot);
    add(l, r, 1, -c[i]);          // 選區間獲利
}
for (i=2; i<=tot; i++) add(i-1, i, k, 0); // 不選
add(tot, sink, k, 0);

// SPFA 求最小費用最大流
// 最終答案 = -cost

SPFA 實現標準最小費用流，費用可為負，無負環。