Antenna Placement poj3020

这是一道比较经典的二分匹配，将格子按黑白标记后，再将含'*'的格子按黑白分成两组，建边。最后的结果就是总的'*'的个数-匹配数。

[cpp]
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>map[400];//按奇偶性建二分图
int t,n,m;
int match[400],fy[400],ln,rn;
int map1[41][11];//原始图
int dirt[4][2]={0,1,0,-1,1,0,-1,0};

int path(int u)
{
    for(int i=0,j;i<map[u].size();i++)
    {
        j=map[u][i];
        if(!fy[j])
        {
            fy[j]=1;
            if(match[j]==-1||path(match[j]))
            {
                match[j]=u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int i,j,x,y,ans;
    char tmp;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        ln=rn=0;
        for(i=1;i<=n;i++)
        {
            getchar();
            for(j=1;j<=m;j++)
            {
                scanf("%c",&tmp);
                if(tmp=='*')
                {
                    if((i+j)&1)//奇点
                        map1[i][j]=++ln;
                    else//偶点
                        map1[i][j]=++rn;
                }
                else
                    map1[i][j]=0;
            }
        }
        for(i=1;i<=ln;i++)
            map[i].clear();
        for(i=1;i<=rn;i++)
            match[i]=-1;

        //建二分图
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if(!map1[i][j]||!((i+j)&1))
                    continue;
                for(int k=0;k<4;k++)
                {
                    x=i+dirt[k][0];
                    y=j+dirt[k][1];
                    if(x<=0||x>n||y<=0||y>m||!map1[x][y])
                        continue;
                    map[map1[i][j]].push_back(map1[x][y]);
                }
            }

        //求最大匹配
        ans=0;
        for(i=1;i<=ln;i++)
        {
            for(j=1;j<=rn;j++)
                fy[j]=0;
            if(path(i))
                    ans++;
        }
        printf("%d\n",ln+rn-ans);
    }
    return 0;
}

补充：软件开发 , C++ ,