問(wèn)題:
http://poj.org/problem?id=2536思路:
典型的最大二分匹配，也是咱的第一道最大二分匹配
根據(jù)題意，在規(guī)定的時(shí)間和速度下，gopher[i]能夠到達(dá)hole[j]，那么在i與j之間存在一條邊，這樣就建立了二分圖
學(xué)習(xí)了匈牙利算法，見(jiàn)
http://www.shnenglu.com/Joe/archive/2010/10/20/130573.html代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #include<math.h>
5 #define MAX_LEN 101
6 int map[MAX_LEN][MAX_LEN];
7 int result[MAX_LEN]; /* previous matching */
8 int state[MAX_LEN];
9 int n, m, s, v;
10 struct Coordinate {
11 float x, y;
12 }gophers[MAX_LEN], holes[MAX_LEN];
13
14 int
15 findpath(int u)
16 {
17 int i;
18 for(i=0; i<m; i++) {
19 if(map[u][i] && state[i]==-1) {
20 state[i] = 1;
21 if(result[i]==-1 || findpath(result[i])) {
22 result[i] = u; /* 取反 */
23 return 1;
24 }
25 }
26 }
27 return 0;
28 }
29
30 int
31 MaxMatch()
32 {
33 int i, ans = 0;
34 for(i=0; i<n; i++) {
35 memset(state, -1, sizeof(state));
36 if(findpath(i))
37 ++ans;
38 }
39 return ans;
40 }
41
42 int
43 main(int argc, char **argv)
44 {
45 int i, j;
46 while(scanf("%d %d %d %d", &n, &m, &s, &v) != EOF) {
47 for(i=0; i<n; i++)
48 scanf("%f %f", &gophers[i].x, &gophers[i].y);
49 for(j=0; j<m; j++)
50 scanf("%f %f", &holes[j].x, &holes[j].y);
51
52 memset(map, 0, sizeof(map));
53 memset(result, -1, sizeof(result));
54 for(i=0; i<n; i++)
55 for(j=0; j<m; j++) {
56 if(sqrt((holes[j].x-gophers[i].x)*(holes[j].x-gophers[i].x) + (holes[j].y-gophers[i].y)*(holes[j].y-gophers[i].y)) <= v*s) /*reachable*/
57 map[i][j] = 1;
58 else
59 map[i][j] = 0;
60 }
61
62 printf("%d\n", n-MaxMatch());
63 }
64 }