Antenna Placement(二分图的最大匹配)

题意：

一个矩形中，有N个城市'*'，现在这n个城市都要覆盖无线，若放置一个基站，它至多可以覆盖相邻的两个城市。
问至少放置多少个基站才能使得所有的城市都覆盖无线？

无向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数/2

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N=505;
 4 int pos[N][N],map[N][N];
 5 int link[N];
 6 bool vis[N];
 7 int dir[4][2] = {{0,-1},{0,1},{1,0},{-1,0}};
 8 int n;
 9 int dfs(int x)
10 {
11     for (int i = 1; i <= n; i++)
12     {
13         if (map[x][i]&&!vis[i])
14         {
15             vis[i] = true;
16             if(!link[i]||dfs(link[i]))
17             {
18                 link[i] = x;
19                 return 1;
20             }
21         }
22     }
23     return 0;
24 }
25 int main()
26 {
27     char ch;
28     int t,h,w;
29     scanf("%d",&t);
30     while(t--)
31     {
32         int id = 0;
33         int ans = 0;
34         scanf("%d%d%*c",&h,&w);
35         memset(pos,0,sizeof(pos));
36         memset(map,0,sizeof(map));
37         memset(link,0,sizeof(link));
38         for(int i = 1; i <= h; i++)
39         {
40             for (int j = 1; j <= w; j++)
41             {
42                 scanf("%c",&ch);
43                 if (ch=='*')
44                     pos[i][j] = ++id;
45             }
46             getchar();
47         }
48         for (int i = 1; i <= h; i++)
49         {
50             for (int j = 1; j <= w; j++)
51             {
52                 if(pos[i][j])
53                     for (int k = 0; k < 4; k++)
54                     {
55                         int dx = i+dir[k][0];
56                         int dy = j+dir[k][1];
57                         if(pos[dx][dy])
58                         {
59                             map[pos[i][j]][pos[dx][dy]] = 1;
60                         }
61                     }
62             }
63         }
64         n = id;
65         for (int i = 1; i <= n; i++)
66         {
67             memset(vis,0,sizeof(vis));
68             if(dfs(i))
69                 ans++;
70         }
71         printf("%d
",n-ans/2);//无向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数/2
72     }
73     return 0;
74 }

View Code