题目地址：Antenna Placement
题目大意：
给你一个图里面包含“o”和“*”，*表示需要天线覆盖的区域，已知天线每次最多可以覆盖相邻的两哥*。问最少需要几个*。
解题思路：
利用二分匹配，这里不是一个集合向另一个集合的定点建图，而是由一个*点的位置向四周有*的位置建图。因为一般的二分匹配是单向边，而这个图建的是双向边
所以找到的最大匹配需要除以2.
最少需要天线的个数： 最大匹配数/2+未匹配数 而未匹配数＝*的总数－匹配数/2×2＝*的总数－匹配数 所以答案是*的总数－最大匹配数/2。
代码：
1 /*两个代码：一个是输入建图匹配的时候上下左右寻找。一个是先利用*的上下左右建图。*/ 2 #include <algorithm> 3 #include <iostream> 4 #include <sstream> 5 #include <cstdlib> 6 #include <cstring> 7 #include <cstdio> 8 #include <string> 9 #include <bitset> 10 #include <vector> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <list> 15 //#include <map> 16 #include <set> 17 using namespace std; 18 /***************************************/ 19 #define ll long long 20 #define int64 __int64 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {-1,1,0,0}; 26 const int d1y[]= {0,0,-1,1}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 /***************************************/ 32 void openfile() 33 { 34 freopen("data.in","rb",stdin); 35 freopen("data.out","wb",stdout); 36 } 37 /**********************华丽丽的分割线,以上为模板部分*****************/ 38 #define MAXN 505 39 int nx,ny; 40 int G[MAXN][MAXN]; 41 int cx[MAXN][MAXN],cy[MAXN][MAXN]; 42 int vis[MAXN][MAXN]; 43 int path(int x1,int y1) 44 { 45 int i; 46 int x,y; 47 for(i=0; i<4; i++) 48 { 49 x=x1+d1x[i]; 50 y=y1+d1y[i]; 51 if (G[x][y]&&!vis[x][y]) 52 { 53 vis[x][y]=-1; 54 if (cy[x][y]==-1||path(cx[x][y],cy[x][y])) 55 { 56 cx[x][y]=x1; 57 cy[x][y]=y1; 58 return 1; 59 } 60 } 61 } 62 return 0; 63 } 64 int MaxMatch() 65 { 66 int cnt=0; 67 memset(cx,-1,sizeof(cx)); 68 memset(cy,-1,sizeof(cy)); 69 int i,j; 70 for(i=0; i<nx; i++) 71 for(j=0; j<ny; j++) 72 { 73 memset(vis,0,sizeof(vis)); 74 if (G[i][j]==1) 75 cnt+=path(i,j); 76 } 77 return cnt; 78 } 79 int main() 80 { 81 int cas; 82 scanf("%d",&cas); 83 while(cas--) 84 { 85 // int m; 86 scanf("%d%d",&nx,&ny); 87 int i,j; 88 int x,y; 89 int min=0; 90 int sum=0; 91 char c; 92 memset(G,0,sizeof(G)); 93 getchar(); 94 for(i=0; i<nx; i++) 95 { 96 for(j=0; j<ny; j++) 97 { 98 scanf("%c",&c); 99 if (c=='*') 100 { 101 G[i][j]=1; 102 sum++; 103 } 104 } 105 getchar(); 106 } 107 min+=MaxMatch(); 108 min=sum-min/2; 109 printf("%d ",min); 110 } 111 return 0; 112 } 113 /*********************************************/ 114 #include <algorithm> 115 #include <iostream> 116 #include <sstream> 117 #include <cstdlib> 118 #include <cstring> 119 #include <cstdio> 120 #include <string> 121 #include <bitset> 122 #include <vector> 123 #include <queue> 124 #include <stack> 125 #include <cmath> 126 #include <list> 127 #include <map> 128 #include <set> 129 using namespace std; 130 /***************************************/ 131 typedef vector<int> VI; 132 typedef vector<char> VC; 133 typedef vector<string> VS; 134 typedef set<int> SI; 135 typedef set<string> SS; 136 typedef map<int ,int> MII; 137 typedef map<string,int> MSI; 138 typedef pair<int,int> PII; 139 typedef vector<PII> VII; 140 typedef vector<VI > VVI; 141 /***************************************/ 142 #define clr(a,b) memset(a,b,sizeof(a)) 143 #define all(x) (x).begin(), (x).end() 144 #define sz(x) ((int)(x).size()) 145 #define ll long long 146 #define int64 __int64 147 #define pb push_back 148 #define mp make_pair 149 #define LL(x) ((x)<<1) 150 #define RR(x) ((x)<<1|1) 151 #define ri(x) scanf("%d",&x) 152 #define rii(x,y) scanf("%d%d",&x,&y) 153 #define rd(x) scanf("%lf",&x) 154 #define rdd(x,y) scanf("%lf%lf",&x,&y) 155 #define rs(x) scanf("%s",x) 156 #define pi(x) printf("%d",x) 157 #define pin(x) printf("%d ",x) 158 #define ps(x) printf("%s",x) 159 #define pn() printf(" ") 160 #define sqr(x) ((x)*(x)) 161 #define rep(i,a,b) for(int i=(a);i<(b);i++) 162 #define repu(i,a,b) for(int i=(a);i<=(b);i++) 163 #define repd(i,a,b) for(int i=(a);i>=(b);i--) 164 #define repc(i,a,c) for(int i=(a);(c);i++) 165 /***************************************/ 166 const int INF = 0x7f7f7f7f; 167 const double eps = 1e-8; 168 const double PIE=acos(-1.0); 169 const int dx[]= {0,1,0,-1}; 170 const int dy[]= {1,0,-1,0}; 171 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 172 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 173 /***************************************/ 174 void openfile() 175 { 176 freopen("data.in","rb",stdin); 177 freopen("data.out","wb",stdout); 178 } 179 /**********************The End OF The Template*****************/ 180 181 const int N = 410; 182 char edge[45][15]; 183 int h,w; 184 vector<int>graph[N]; 185 int mx[N],my[N],vis[N]; 186 187 void init() 188 { 189 rep(i,0,N) 190 graph[i].clear(); 191 clr(mx,-1); 192 clr(my,-1); 193 } 194 195 int dfs(int u) 196 { 197 rep(i,0,(int)graph[u].size()) 198 { 199 int v=graph[u][i]; 200 if(!vis[v]) 201 { 202 vis[v]=1; 203 if(my[v]==-1||dfs(my[v])) 204 { 205 my[v]=u; 206 mx[u]=v; 207 return 1; 208 } 209 } 210 } 211 return 0; 212 } 213 214 int hungray() 215 { 216 int cnt=0; 217 rep(i,0,w*h) 218 { 219 if(mx[i]==-1) 220 { 221 clr(vis,0); 222 if(dfs(i)) cnt++; 223 } 224 } 225 return cnt; 226 } 227 228 int main() 229 { 230 int T; 231 ri(T); 232 while(T--) 233 { 234 init(); 235 rii(h,w); 236 rep(i,0,h) 237 rs(edge[i]); 238 int ans=0; 239 rep(i,0,h) 240 { 241 rep(j,0,w) 242 { 243 if(edge[i][j]=='*') 244 { 245 ans++; 246 int x=i*w+j; 247 rep(k,0,4) 248 { 249 int newx=i+dx[k]; 250 int newy=j+dy[k]; 251 if(newx>=0&&newx<h&&newy>=0&&newy<w&&edge[newx][newy]=='*') 252 { 253 int y=newx*w+newy; 254 graph[x].push_back(y); 255 } 256 } 257 } 258 } 259 } 260 //pin(hungray()/2); 261 printf("%d ",ans-hungray()/2); 262 } 263 return 0; 264 }