传送门：HDU - 2389
题意：花园里有m个人，n把伞，伞和人的位置用坐标表示，每个人有一个行进速度，t时间之后会下雨，现在要知道在怎样分配，使得更多的人拿到伞。
求出每个人到每把伞之间的距离，如果距离小于等于下雨之前时间t与人的速度的乘积，就连一条从人到伞的单向边，通过这种方式就可以把题目转换成求二分图最大匹配的问题，但是由于数据范围太大所以要使用Hopcroft-Karp算法。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAX_N = 6010;
const int MAX_M = 3010*3010;
int time;
int n, m;
int x[MAX_N], y[MAX_N], z[MAX_N];//伞和人的位置都放在x和y数组中
int match[MAX_N];
int dis[MAX_N];
int head[MAX_N], cnt = 1;
struct edge {int v, nxt;
}e[MAX_M];
void add(int u, int v) {e[cnt].v = v;e[cnt].nxt = head[u];head[u] = cnt++;
}
bool bfs() {queue<int>q;bool flag = false;memset(dis, 0, sizeof dis);for (int i = 1; i <= m; i++) {if (match[i] == -1) {q.push(i);}}while (!q.empty()) {int temp = q.front();q.pop();for (int i = head[temp]; ~i; i = e[i].nxt) {int v = e[i].v;if (!dis[v]) {dis[v] = dis[temp] + 1;if (match[v] == -1) { flag = true;}else {dis[match[v]] = dis[v] + 1;q.push(match[v]);}}}}if (flag)return true;return false;
}bool dfs(int x) {for (int i = head[x]; ~i; i = e[i].nxt) {int v = e[i].v;if (dis[v] != dis[x] + 1)continue;dis[v] = -1;if (match[v] == -1 || dfs(match[v])) {match[v] = x;match[x] = v;return true;}}return false;
}
int main() {int t;cin >> t;int k = 0;while (t--) {memset(head, -1, sizeof head);memset(match, -1, sizeof match);k++;cnt = 1;scanf("%d", &time);scanf("%d", &m);for (int i = 1; i <= m; i++) {scanf("%d%d%d", &x[i], &y[i], &z[i]);}scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d%d", &x[i + m], &y[i + m]);}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {int u = j;int v = m + i;int w = (x[u] - x[v]) * (x[u] - x[v]) + (y[u] - y[v]) * (y[u] - y[v]);int temp = (time * z[u]) * (time * z[u]);if (temp >= w) { add(u, v);}}}int ans = 0;while (bfs()) {for (int i = 1; i <= m; i++) {if (match[i] == -1) {if (dfs(i))ans++;}}}printf("Scenario #%d:\n", k);printf("%d\n\n", ans);}return 0;
}