poj 2536/caioj 1124(二分图最大匹配)

poj 2536
二分图最大匹配裸题,这里用最大流dinic做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 200 + 10, MAXM = 20000 + 10, INF = 2147483647;
const db eps = 1e-12;
struct data {
int v, cap, flow;
}ed[MAXM];
struct pos {db x, y;}p[MAXN];
vector<int> G[MAXN];
int en, n, m, S, V, s, t;
bool canConnect(int l, int r) {
db dis = (p[l].x - p[r + n].x) * (p[l].x - p[r + n].x) + (p[l].y - p[r + n].y) * (p[l].y - p[r + n].y);
if ((db)S * S * V * V - dis >= eps) return true;
return false;
}
void ins(int u, int v, int c) {
ed[en] = (data){v, c, 0}, G[u].push_back(en++);
ed[en] = (data){u, 0, 0}, G[v].push_back(en++);
}
void clean() {
en = 0, s = n + m + 1, t = n + m + 2;
for (int i = 0; i <= n + m + 2; i++) G[i].clear();
}
int cur[MAXN], vis[MAXN], d[MAXN];
bool bfs() {
queue<int> q;
for (int i = 1; i <= n + m + 2; i++) d[i] = INF, vis[i] = false;
q.push(s), d[s] = 0, vis[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)G[u].size(); i++) {
int v = ed[G[u][i]].v, flow = ed[G[u][i]].flow, cap = ed[G[u][i]].cap;
if (!vis[v] && cap > flow) {
d[v] = d[u] + 1, vis[v] = true;
q.push(v);
}
}
}
return vis[t];
}
int dfs(int u, int a) {
if (u == t) return a;
if (a == 0) return 0;
int retflow = 0;
for (int &i = cur[u]; i < (int)G[u].size(); i++) {
int v = ed[G[u][i]].v, flow = ed[G[u][i]].flow, cap = ed[G[u][i]].cap;
if (d[v] == d[u] + 1) {
if (cap > flow) {
int f = dfs(v, min(a, cap - flow));
if (f > 0) {
a -= f, retflow += f;
ed[G[u][i]].flow += f, ed[G[u][i] ^ 1].flow -= f;
}
if (a == 0) break;
}
}
}
return retflow;
}
int dinic() {
int flow = 0;
while (bfs()) {
for (int i = 0; i <= n + m + 2; i++) cur[i] = 0;
flow += dfs(s, INF);
}
return flow;
}
void solve() {
clean();
for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
for (int i = 1; i <= m; i++) scanf("%lf%lf", &p[i + n].x, &p[i + n].y);
for (int i = 1; i <= n; i++) ins(s, i, 1);
for (int i = 1; i <= m; i++) ins(i + n, t, 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (canConnect(i, j)) {
ins(i, j + n, 1);
}
}
}
printf("%d\n", n - dinic());
}
int main() {
while (scanf("%d%d%d%d", &n, &m, &S, &V) == 4) solve();
return 0;
}
------ 本文结束 ------