POJ 3020-Antenna Placement-二分图匹配

题意：一个N*M的矩阵里有K个观测点，你必须放置天线覆盖所有观测点。每个雷达只能天线两个观测点，这两点必须相邻。计算最少天线数。

做法：将所有相邻的观测点连起来，建图。跑一遍匈牙利算法就计算出了最大的覆盖数，除以二就是天线数。还要加上落单的观测点，每个都需要一个天线。

 /*--------------------------------------------------------------------------------------*/

 //        Helica's header

 //        Second Edition

 //        2015.11.7

 //

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <ctype.h>

 #include <cstdlib>

 #include <cstdio>

 #include <vector>

 #include <string>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <set>

 #include <map>

 //debug function for a N*M array

 #define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++)\

 {for(int j=;j<(M);j++){\

 printf("%d",G[i][j]);}printf("\n");}

 //debug function for int,float,double,etc.

 #define debug_var(X) cout<<#X"="<<X<<endl;

 /*--------------------------------------------------------------------------------------*/

 using namespace std;

 const int maxn = ;

 int N,M,T;

 int G[*maxn][*maxn],Map[maxn][maxn];

 int dx[]={,-,,},dy[]={,,,-};

 int linker[*maxn];

 bool used[*maxn];

 int uN,vN;

 bool dfs(int u)

 {

     for(int v=;v<=vN;v++)

     {

         if(G[u][v] && !used[v])

         {

             used[v] = true;

             if(linker[v] == - || dfs(linker[v]))

             {

                 linker[v] = u;

                 return true;

             }

         }

     }

     return false;

 }

 int hungary()

 {

     memset(linker,-,sizeof linker);

     int res = ;

     for(int u=;u<=uN;u++)

     {

         memset(used,false,sizeof used);

         if(dfs(u)) res++;

     }

     return res;

 }

 int main()

 {

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&N,&M);

         char c;

         uN = ;

         for(int i=;i<N;i++)

         {

             getchar();

             for(int j=;j<M;j++)

             {

                 scanf("%c",&c);

                 if(c == '*') Map[i][j] = ++uN;

                 else Map[i][j] = ;

             }

         }

         memset(G,,sizeof G);

         vN = uN;

         for(int i=;i<N;i++)

         {

             for(int j=;j<M;j++) if(Map[i][j])

             {

                 int u = Map[i][j];

                 for(int p=;p<;p++)

                 {

                     int nx = i+dx[p],ny = j+dy[p];

                     if(nx >= && nx < N && ny >= && ny < M)

                     {

                         if(int v = Map[nx][ny])

                            {

                             //printf("u:%d v:%d\n",u,v);

                             G[u][v] = G[v][u] = ;

                         }

                     }

                 }

             }

         }

         int ans = hungary();

         //printf("ans:%d uN:%d\n",ans,uN);

         printf("%d\n",(uN-ans)+ans/);

     }

 }