HDU 4406 GPA：最大費用最大流優化復習安排

題目大意

n 天、每天上 k 門課、m 門課總數。每門課有學分 w、基礎分 score。給定每天可復習的課程。GPA 計算公式：

f(score, w) = w × (4 - 3/1600 × (100 - score)²)

安排復習使 GPA 最大且無不及格（score ≥ 60）。

建模：最大費用最大流

• 源點 S，匯點 T。
• 每天節點 Day_i → T，容量 k，費用 0。
• 每門課節點 Course_j → Day_i（若該天可復習），容量 k，費用 0。
• S → Course_j 分段連邊：
  • 若 score < 60：先連一條容量 60-score、費用 INF 的邊（強制優先刷到 60），再對 61~100 每分連容量 1、費用 f(x)-f(x-1) 的邊。
  • 若 score ≥ 60：對 score+1 ~ 100 每分連容量 1、費用增量的邊。

跑最大費用最大流（SPFA 找增廣路）。流量即總復習次數，費用即 GPA 分子增量。最後檢查是否有課程 score < 60，若有輸出 0，否則計算 GPA = 總費用 / 總學分。

參考代碼框架 (C++ 關鍵結構)

struct Edge { int v, cap, flow; double cost; int next; };
vector edges; vector head;
void addEdge(int u, int v, int cap, double cost) { ... } // 雙向邊，反向費用取負

bool spfa(int s, int t, int& flow, double& cost) { ... } // 尋找最大費用增廣路
double maxCostFlow(int s, int t) { ... } // 循環調用 SPFA

double gain(int score, int w) { 
    return w * (4.0 - 3.0 * (100-score)*(100-score) / 1600.0); 
}

// 主流程：建圖 → maxCostFlow → 檢查及格 → 輸出 GPA

關鍵點

• 費用為增量 f(x) - f(x-1)，保證每單位流量增益正確。
• INF 費用強制優先滿足及格線（最小費用流中用負費用，此處為最大費用流用大正費用）。
• 節點數 ~ n+m ≤ 100+50，邊數可控，SPFA 足夠快。