hdu 3360 最小点覆盖 **

题意:给你一个图，图中有宝物和保安两种元素。每个宝物需要周围的某些位置同时安放保安（如果那些位置有宝物，可以把宝物替换成保安）问你最少需要再安置多少保安，可以使所有宝物满足要求。

题意有点难懂

链接：点我

直接建无向图，少判断个奇偶性，最后除个2即可

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 typedef long long ll;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN = ;//点数的最大值

 const int MAXM = ;//边数的最大值

 int a[MAXN][MAXN];

 int b[MAXN][MAXN];

 int n,m,tt;

 /*

 * 匈牙利算法邻接表形式

 * 使用前用init()进行初始化，给uN赋值

 * 加边使用函数addedge(u,v)

 *

 */

 struct Edge

 {

     int to,next;

 }edge[MAXM];

 int head[MAXN],tot;

 void init()

 {

     tot = ;

     memset(head,-,sizeof(head));

 }

 void addedge(int u,int v)

 {

     edge[tot].to = v; edge[tot].next = head[u];

     head[u] = tot++;

 }

 int linker[MAXN];

 bool used[MAXN];

 int uN;

 bool dfs(int u)

 {

     for(int i = head[u]; i != - ;i = edge[i].next)

     {

         int v = edge[i].to;

         if(!used[v])

         {

             used[v] = true;

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

             {

                 linker[v] = u;

                 return true;

             }

         }

     }

     return false;

 }

 int hungary()

 {

     int res = ;

     memset(linker,-,sizeof(linker));

     for(int u = ; u < uN;u++)//点的编号0~uN-1

     {

         memset(used,false,sizeof(used));

         if(dfs(u))res++;

     }

     return res;

 }

 int dir[][] = {{-,-},{-,-},{-,},{-,},{,},

 {,},{,-},{,-},{-,},{,},{,},{,-}};

 int main()

 {

     int i,j,k;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     int ca=;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         if(n==&&m==)  break;

         uN = ;

         for(i = ;i < n;i++)

             for(j = ;j < m;j++)

             {

                 b[i][j] = uN++;

             }

         for(i=;i<n;i++)

         {

             for(j=;j<m;j++)

             {

                 scanf("%d",&a[i][j]);

             }

         }

         init();

         for(i=;i<n;i++)

         {

             for(j=;j<m;j++)

             {

                 if(a[i][j]!=-)

                 {

                     for(k=;k<;k++)

                     {

                         if(a[i][j]&(<<k))  //该点需要放置守卫

                         {

                             int nx=i+dir[k][];

                             int ny=j+dir[k][];

                             if(nx>=&&nx<n&&ny>=&&ny<m&&a[nx][ny]!=-)

                             {

                                 addedge(b[i][j],b[nx][ny]);

                                 addedge(b[nx][ny],b[i][j]);

                             }

                         }

                     }

                 }

             }

         }

         printf("%d. %d\n",ca++,hungary()/);

     }

 }