雨中避雨问题（HDU2389）——Hopcroft-Karp算法应用

在一个场景中，有 n 把雨伞和 m 个人，t 分钟后开始下雨。每个人只能使用一把雨伞，且每把雨伞只能被一个人使用。目标是在下雨时，尽可能多的人能够拿到雨伞。

该问题可以通过二分图的最大匹配来解决。具体步骤如下：

1. 将问题建模为一个二分图，其中一边是雨伞，另一边是人。
2. 计算每个人到每把雨伞的距离，如果某人在 t 分钟内可以到达某把雨伞，则在这两个节点之间建立一条边。
3. 使用 Hopcroft-Karp 算法求解二分图的最大匹配。

#include 
#include 
#include 
#include 
#include 
#define EDGE(int _to, int _next)
#define to(_to), next(_next)
#define ll long long
using namespace std;
typedef pair P;
const int maxn = 6050; // 存储的点最多是 n + m
int vis[maxn];
struct EDGE {
    int to, next;
    EDGE() {}
    EDGE(int _to, int _next) : to(_to), next(_next) {}
} e[maxn * 1500];
int cnt, n, m, p, ca = 0, T, t;
int head[maxn], con[maxn], dep[maxn];
int x[maxn], y[maxn], s[maxn];
void add(int bg, int to) {
    e[++cnt] = EDGE(to, head[bg]);
    head[bg] = cnt;
}
void init() {
    cnt = 0;
    memset(head, -1, sizeof head);
    memset(vis, 0, sizeof vis);
    memset(con, -1, sizeof con); // 初始化 con 为 -1
    cin >> t >> n;
    for (int i = 1; i <= n; ++i) scanf("%d%d%d", &x[i], &y[i], &s[i]);
    cin >> m;
    for (int i = 1; i <= m; ++i) scanf("%d%d", &x[i + n], &y[i + n]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            int w = (x[i] - x[j + n]) * (x[i] - x[j + n]) + (y[i] - y[j + n]) * (y[i] - y[j + n]);
            int temp = t * s[i] * t * s[i];
            if (temp >= w) add(i, j + n);
        }
}
bool bfs() {
    memset(dep, 0, sizeof dep);
    queue q;
    while (q.size()) q.pop();
    for (int i = 1; i <= n; ++i)
        if (con[i] == -1) q.push(i);
    bool flag = 0;
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = e[i].next) {
            if (!dep[e[i].to]) {
                dep[e[i].to] = dep[u] + 1;
                if (con[e[i].to] == -1) flag = 1;
                else dep[con[e[i].to]] = dep[e[i].to] + 1, q.push(con[e[i].to]);
            }
        }
    }
    return flag;
}
bool dfs(int u) {
    for (int i = head[u]; i != -1; i = e[i].next) {
        int v = e[i].to;
        if (dep[v] != dep[u] + 1) continue;
        dep[v] = 0;
        if (con[v] == -1 || dfs(con[v])) {
            con[u] = v;
            con[v] = u;
            return 1;
        }
    }
    return 0;
}
void sol() {
    int ans = 0;
    while (bfs())
        for (int i = 1; i <= n; ++i)
            if (con[i] == -1 && dfs(i)) ans++;
    printf("Scenario #%d:\n%d\n\n", ++ca, ans);
}
int main() {
    cin >> T;
    while (T--) {
        init();
        sol();
    }
}