HDU 3360 National Treasures 奇偶匹配的最低点覆盖

标题来源：

意甲冠军：假设a[i][j] ！= -1 把他转成二进制最多有12位代表题目那张图的12个位置假设相应位是1 说明在那里放一个守卫能够看住a[i][j]位置上的这个东西

思路：明显死最小点覆盖奇偶匹配建图

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int maxn = 55;

int vis[maxn*maxn];

int y[maxn*maxn];

vector <int> G[maxn*maxn];

int n, m;

int a[maxn][maxn];

int dir[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};

bool dfs(int u)

{

    for(int i = 0; i < G[u].size(); i++)

    {

        int v = G[u][i];

        if(vis[v])

            continue;

        vis[v] = true;

        if(y[v] == -1 || dfs(y[v]))

        {

            y[v] = u;

            return true;

        }

    }

    return false;

}

int match()

{

    int ans = 0;

    memset(y, -1, sizeof(y));

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

    {

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

        {

        	if((i+j)%2)

			{

				memset(vis, 0, sizeof(vis));

        		if(dfs(i*m+j))

        		    ans++;

			}

        }

    }

    return ans;

}

int main()

{

	int cas = 1;

	while(scanf("%d %d", &n, &m) && (n||m))

	{

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

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

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

		for(int i = 0; i < n*m; i++)

			G[i].clear();

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

		{

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

			{

				int x = a[i][j];

				if(x == -1)

					continue;

				for(int k = 0; k < 12; k++, x >>= 1)

				{

					if(!x)

						break;

					if(!(x&1))

						continue;

					int xx = i + dir[k][0];

					int yy = j + dir[k][1];

					if(xx < 0 || xx >= n || yy < 0 || yy >= m)

						continue;

					if(a[xx][yy] == -1)

						continue;

					if((i+j)%2)

						G[i*m+j].push_back(xx*m+yy);

					else

						G[xx*m+yy].push_back(i*m+j);

				}

			}

		}

		printf("%d. %d\n", cas++, match());

	}

    return 0;

}