Antenna Placement poj 3020(匹配)

http://poj.org/problem?id=3020

题意：给定一个n*m的矩阵，'*'代表城市，现在想要用1*2的矩阵将所有的城市覆盖，问最少需要多少个矩阵？

分析：先为每个城市进行标号，再构建图，用匈牙利算法算出最大匹配。由于这里面用了双向边进行构图，所以最终所求答案为点集数-匹配数/2.

点集数-匹配数/2 = 点集数-匹配数/2*2+匹配数/2（单独的一个点的+匹配成功的点/2）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;
typedef long long LL;

const int maxn=1010;
const int INF=0x3f3f3f3f;
const int mod=2009;
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
char maps[maxn][maxn];
int G[maxn][maxn],a[maxn][maxn], v[maxn], used[maxn];
int p, n, m;

int Hungary(int x)
{
    for(int i=1; i<=p; i++)
    {
        if(!v[i] && G[x][i])
        {
            v[i]=1;
            if(!used[i] || Hungary(used[i]))
            {
                used[i] = x;
                return 1;
            }
        }
    }
    return 0;
}

int OK(int x, int y)
{
    if(x>=0 && x<n && y>=0 &&y<m && maps[x][y]=='*')
        return 1;
    return 0;
}

int main()
{
    int T;

    scanf("%d", &T);

    while(T --)
    {
        scanf("%d %d", &n, &m);

        for(int i=0; i<n; i++)
            scanf("%s", maps[i]);

        memset(G, 0, sizeof(G));
        memset(a, 0, sizeof(a));

         p = 0;

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(maps[i][j]=='*')
                    a[i][j]=++p;
            }
        }

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(maps[i][j]=='*')
                {
                    for(int k=0; k<4; k++)
                    {
                       int nx = dir[k][0]+i;
                       int ny = dir[k][1]+j;

                       if(OK(nx, ny))
                       {
                           G[a[i][j]][a[nx][ny]] = 1;
                           G[a[nx][ny]][a[i][j]] = 1;
                       }
                    }
                }
            }
        }

        int ans = 0;
        memset(used, 0, sizeof(used));
        for(int i=1; i<=p; i++)
        {
            memset(v, 0, sizeof(v));
            if(Hungary(i))
                ans ++;
        }

        printf("%d
", p-ans/2);
    }
    return 0;
}