BZOJ 1822 Frozen Nova - 二分答案 + 最大流

問題描述

平面上有巫妖和小精靈，樹木阻擋視線。巫妖有攻擊半徑和技能 CD。在半徑內且視線無阻擋的精靈可被秒殺。求最短時間消滅所有精靈。

建模：二分時間 + 最大流

1. 二分答案 T（時間）。
2. 對於給定 T，每個巫妖可攻擊次數 = T / CD + 1。
3. 構建流網絡：
   • 源點 S 向每個巫妖連邊，容量 = 可攻擊次數。
   • 巫妖向可攻擊的精靈連邊，容量 = 1。
   • 精靈向匯點 T 連邊，容量 = 1。
4. 若最大流 = 精靈總數，則 T 可行。

幾何判斷

• 距離判斷：dist(巫妖, 精靈) <= 半徑。
• 阻擋判斷：線段 (巫妖, 精靈) 與樹木圓是否相交。利用三角形面積法計算點到線段距離，若 ≤ 樹半徑則阻擋。

代碼框架（C++，Dinic 算法）

struct Dinic {
    // 標準 Dinic 實現：BFS 分層 + DFS 增廣
    // 節點數：S=0, 巫妖 1..L, 精靈 L+1..L+R, T=L+R+1
};

bool check(int T) {
    dinic.clear();
    for (int i = 1; i <= L; i++) dinic.addEdge(S, i, T / cd[i] + 1);
    for (int i = 1; i <= L; i++)
        for (int j = 1; j <= R; j++)
            if (canAttack[i][j]) dinic.addEdge(i, L+j, 1);
    for (int j = 1; j <= R; j++) dinic.addEdge(L+j, T, 1);
    return dinic.maxFlow() == R;
}

int main() {
    // 讀入數據，預計算 canAttack 矩陣
    int lo = 0, hi = 1e7, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (check(mid)) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    cout << ans << endl;
}

複雜度

二分 log(1e7) ≈ 24 次。每次 Dinic 在節點數 ≤ 500，邊數 ≤ 250000 圖上極快。總體通過。