学步园

               题意:

                       在R*C上有些艺术品..每个艺术品用非负数表示代表他附近那些格子需要保安...-1代表该格子上本来就是保安..必须保证艺术品关键的位置必须要有保安.或者不放这个艺术品..在这个艺术品上站保安..问最少要增加多少保安满足条件...

               题解:

                       根据每件艺术品所需要的安保条件建边..注意..这个边的意思是两个点需要联系..所以艺术品指向保安和保安指向艺术品是一回事...题目就转化成了二分图的最小点覆盖问题(用最少的点覆盖所有的边..边是需要的安保关系..点是需要增加的保安数量)...等价于求其最大匹配...注意..建图有两种方式..一种是分奇偶点..建成两侧完全不同的点..答案就是跑最大匹配..第二种是两侧都是相同的点..边也是建双向边..答案是最大匹配/2

Program:

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<string.h>
#include<queue>
#define ll long long
#define esp 1e-5
#define MAXN 3005
#define MAXM 500005
#define oo 100000007
using namespace std;    
struct node
{
       int y,next;
}line[MAXM];
int match[MAXN],way[12][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,0},{0,1},{1,0},{0,-1}};
int Lnum,_next[MAXN],arc[MAXN][MAXN];
bool used[MAXN];
void addline(int x,int y)
{
       line[++Lnum].next=_next[x],_next[x]=Lnum,line[Lnum].y=y;
}
bool dfs(int x)
{
       for (int k=_next[x];k;k=line[k].next)
       {
               int y=line[k].y;
               if (used[y]) continue;
               used[y]=true;
               if (!match[y] || dfs(match[y]))
               {
                     match[y]=x;
                     return true;
               }
       } 
       return false;
}
int getmax(int n)
{
       int sum=0;
       memset(match,0,sizeof(match));
       for (int i=0;i<n;i++)
       {
                memset(used,false,sizeof(used));
                sum+=dfs(i);
       }
       return sum;
}
int main()
{            
       int i,cases=0,R,C,x,y,h;
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
       while (~scanf("%d%d",&R,&C) && R)
       { 
               for (y=0;y<R;y++)
                  for (x=0;x<C;x++) 
                     scanf("%d",&arc[y][x]);
               Lnum=0,memset(_next,0,sizeof(_next));
               for (y=0;y<R;y++)
                  for (x=0;x<C;x++)
                  if (arc[y][x]>0)
                  { 
                         h=arc[y][x]; 
                         for (i=0;i<12;i++)
                            if (h&(1<<i))
                            {
                                   int yy=y+way[i][0],xx=x+way[i][1];
                                   if (xx<0 || yy<0 || xx>=C || yy>=R || arc[yy][xx]<0) continue;
                                   addline(y*C+x,yy*C+xx),addline(yy*C+xx,y*C+x);
                            }
                  }
               printf("%d. %d\n",++cases,getmax(R*C)/2);
       }    
       return 0;  
}  
/*
3 4
0    0   512  0
536  512 0    0
0    0   512  0
3 4
0    0   0  0
512  536 0  0
0    0   0  0
0 0

3
1
*/