BZOJ 3265 志願者招募加強版：單純形法模板應用

問題背景

與 BZOJ 3112 類似，給定約束條件求線性規劃最優值。數據規模較大，需高效單純形實現。

模型構建

• 變量：每個志願者是否選擇（0/1），但線性規劃鬆弛為連續 [0,1]，單純形求解後取整（題目保證整數最優解）。
• 約束：每個技能需求的覆蓋數量。
   ∑ a_ij x_j ≥ b_i → 標準形乘 -1 轉 ≤。
   每個志願者最多選一次：x_j ≤ 1。
• 目標：最小化總成本 ∑ c_j x_j → 轉 max -∑ c_j x_j。

單純形模板復用

直接套用標準單純形模板（參考 BZOJ 3112），注意：
- 矩陣維度：約束數 m、變量數 n。
- 初始化增廣矩陣 A[m+1][n+m+1]（含鬆弛變量）。
- 數值精度用 double，EPS=1e-9。
- 結果四捨五入輸出整數。

關鍵代碼片段

// 構建表
for (int i=1;i<=m;++i) {
    for (int j=1;j<=n;++j) A[i][j] = -a_ij; // ≥ 轉 ≤
    A[i][n+i] = 1; // slack
    b[i] = -b_i;
}
for (int j=1;j<=n;++j) {
    A[m+1][j] = 1; // x_j <= 1
    A[m+1][n+m+1] = 1; // slack for this row? actually add more rows
}
// 目標行
for (int j=1;j<=n;++j) c[j] = -cost_j;

具體構表細節視具體題目輸入格式而定，核心單純形循環不變。

總結

BZOJ 3265 是單純形法的直接應用題。關鍵在於正確建模（不等式方向、鬆弛變量、目標函數轉換）並復用穩健的單純形模板。熟練掌握標準模板，能在比賽中快速解決線性規劃問題。