POJ 3308 Paratroopers：二分圖最小割 + 對數轉乘積

題目轉化

• n × m 網格，L 個傘兵坐標 (x, y)。
• 可在任意行/列放置雷射砲：第 i 行成本 r[i]，第 j 列成本 c[j]。
• **總成本 = 所有選中行/列成本的乘積**。
• 目標：消滅所有傘兵，最小化總成本。

關鍵數學轉換

log(a × b × c) = log a + log b + log c → **將乘積最小化轉為加權和最小化**。
邊權設為 log(r[i])、log(c[j])，跑最小割，最後 exp(min_cut) 還原答案。

建模為二分圖最小割

• 源點 S，匯點 T。
• 左集合：行節點 1..n，邊 S → row_i 容量 log(r[i])。
• 右集合：列節點 1..m，邊 col_j → T 容量 log(c[j])。
• 傘兵 (x, y) → 邊 row_x → col_y 容量 INF（強制割掉行或列）。
• 最小割 = 選擇一組行/列覆蓋所有傘兵，權重和最小 = log(乘積) 最小。

Dinic 算法核心實作（雙精度流量）

const double INF = 1e100;
struct Edge { int to, next; double cap; };
vector edges;
vector head, level, cur;

void add_edge(int u, int v, double c) {
    edges.push_back({v, head[u], c}); head[u] = edges.size()-1;
    edges.push_back({u, head[v], 0}); head[v] = edges.size()-1;
}

bool bfs(int S, int T) { /* 建立層次圖 */ }
double dfs(int u, int T, double f) { /* 阻塞流 */ }
double dinic(int S, int T) { /* 主循環 */ }

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m, q; scanf("%d%d%d", &n, &m, &q);
        vector R(n+1), C(m+1);
        for (int i=1;i<=n;++i) scanf("%lf", &R[i]);
        for (int j=1;j<=m;++j) scanf("%lf", &C[j]);
        
        // 初始化圖
        int S = 0, T = n + m + 1;
        head.assign(T+1, -1); edges.clear();
        
        // 建邊
        for (int i=1;i<=n;++i) if (R[i]>0) add_edge(S, i, log(R[i]));
        for (int j=1;j<=m;++j) if (C[j]>0) add_edge(n+j, T, log(C[j]));
        for (int k=0;k