HDU3360 National Treasures

　　由于珠宝的临界点必须放置守卫，一个守卫又有可能同时保护许多个珠宝，发现最后要求的便是二分图的最小点集覆盖，这个二分图是这样建的：对于每一个珠宝，如果其临界点没有守卫，那么就在珠宝和该临界点之间连一条边，这条边是必须被覆盖的，所以当整个二分图所有的边都连好后，所要做的就是求最小点集覆盖。

　　我看到网上很多人的做法有奇偶染色的，我这里写简单了一点，直接建成无向图，那么最终计算得到的为最小点集覆盖的2倍。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <vector>
 6 
 7 using namespace std;
 8 
 9 const int maxn = 2500 + 5;
10 
11 bool vis[maxn];
12 int vs[55][55];
13 int r, c;
14 int link[maxn];
15 vector<int> vt[maxn];
16 
17 int dx[]= {-1, -2, -2, -1, 1, 2,  2,  1, -1, 0, 1,  0};
18 int dy[]= {-2, -1,  1,  2, 2, 1, -1, -2,  0, 1, 0, -1};
19 
20 bool find(int i)
21 {
22     int size = vt[i].size();
23     for(int j = 0; j < size; j ++)
24     {
25         int k = vt[i][j];
26         if(!vis[k])
27         {
28             vis[k] = true;
29             if(link[k] == -1 || find(link[k]))
30             {
31                 link[k] = i;
32                 return true;
33             }
34         }
35     }
36     return false;
37 }
38 
39 void init()
40 {
41     for(int i = 0; i <= r * c; i ++)
42         vt[i].clear();
43     memset(vs, 0, sizeof vs);
44     memset(link, -1, sizeof link);
45 }
46 
47 int main()
48 {
49     int t = 1;
50     while(scanf("%d%d", &r, &c) == 2 && r + c)
51     {
52         init();
53         for(int i = 1; i <= r; i ++)
54         {
55             for(int j = 1; j <= c; j ++)
56             {
57                 scanf("%d", &vs[i][j]);
58             }
59         }
60         for(int i = 1; i <= r; i ++)
61         for(int j = 1; j <= c; j ++)
62             if(vs[i][j] != -1)
63             {
64                 for(int k = 0; k < 12; k ++)
65                 {
66                     if((vs[i][j] >> k) & 1)
67                     {
68                         int x = i + dx[k];
69                         int y = j + dy[k];
70                         if(x >= 1 && x <= r && y >= 1 && y <= c && vs[x][y] != -1)
71                         {
72                             vt[c * (i - 1) + j].push_back(c * (x - 1) + y);
73                             vt[c * (x - 1) + y].push_back(c * (i - 1) + j);
74                         }
75                     }
76                 }
77             }
78         int ans = 0;
79         for(int i = 1; i <= c * r; i ++)
80         {
81             memset(vis, false, sizeof vis);
82             ans += find(i);
83         }
84         printf("%d. %d\n", t++, ans / 2);
85     }
86     return 0;
87 }