HDU 2389 Rain on your Parade：Hopcroft-Karp 算法解二分圖最大匹配

問題模型

客人與雨傘為二分圖兩側。客人 i 位置 (x_i,y_i)，速度 v_i，時間 t 內可達雨傘 j（位置 (u_j,v_j)）當且僅當 v_i * t ≥ dist(i,j)。求最大匹配數（每人一傘，每傘一人）。

Hopcroft-Karp 算法

分層 BFS + 多條增廣路 DFS，時間 O(E√V)，V ≤ 6000, E ≤ 9e6（稠密），需優化建圖。

關鍵優化

• 建圖時預計算距離平方，避免 sqrt：v_i*t ≥ dist ⇔ (v_i*t)^2 ≥ dx^2+dy^2
• 鄰接表存儲，vector 或靜態數組
• BFS 分層：dx[u] 為左側節點層次，dy[v] 為右側，dis 記錄未匹配右側節點最小層次
• DFS 尋找增廣路僅沿分層圖

核心代碼結構

struct Guest { int x, y; double r; }; // r = v*t
struct Umbrella { int x, y; };

bool bfs() { /* 分層，返回是否存在增廣路 */ }
bool dfs(int u) { /* 在分層圖中尋找增廣路 */ }
int hopcroftKarp() { /* 循環 BFS+DFS */ }

複雜度

• 建圖：O(G·U) ≈ 9e6，單測試用例 1-2 秒
• Hopcroft-Karp：O(E√V) ≈ 9e6 * 77 ≈ 7e8 操作，實測 546ms AC（測試數據較稀疏）

完整代碼見原文（含靜態數組優化版）