POJ 2536 Gopher II：二分圖最大匹配求倖存老鼠數

POJ 2536 Gopher II：二分圖最大匹配

n 隻老鼠、m 個洞，給出坐標。老鼠速度 v，s 秒後老鷹出現。求被吃掉的老鼠數（即無法在 s 秒內進洞的老鼠數）。

解題思路

構建二分圖：左部老鼠、右部洞。若老鼠 i 到洞 j 的距離 / v ≤ s，則連邊。跑最大匹配（匈牙利 DFS），匹配數即為倖存老鼠數。答案 = n - 匹配數。

代碼實現

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define init(a) memset(a, 0, sizeof(a))
using namespace std;
const int maxn = 310;
int n, m, s, v, ma[500][500];
bool vis[500];
int line[500];
struct node { double x, y; } g[300], h[300];
int DFS(int u) {
    for (int v = 1; v <= m; v++) {
        if (!vis[v] && ma[u][v]) {
            vis[v] = 1;
            if (line[v] == -1 || DFS(line[v])) {
                line[v] = u; return 1;
            }
        }
    }
    return 0;
}
int K_M() {
    memset(line, -1, sizeof(line));
    int ans = 0;
    for (int i = 1; i <= n; i++) { init(vis); ans += DFS(i); }
    return ans;
}
int main() {
    while (scanf("%d%d%d%d", &n, &m, &s, &v) != EOF) {
        init(ma);
        for (int i = 1; i <= n; i++) scanf("%lf%lf", &g[i].x, &g[i].y);
        for (int i = 1; i <= m; i++) scanf("%lf%lf", &h[i].x, &h[i].y);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                double dis = sqrt((h[j].x - g[i].x)*(h[j].x - g[i].x) + (h[j].y - g[i].y)*(h[j].y - g[i].y));
                if (dis / v <= (double)s) ma[i][j] = 1;
            }
        int ans = K_M();
        printf("%d\n", n - ans);
    }
    return 0;
}

經典二分圖匹配模板題，注意浮點數比較精度。