最小路径覆盖

POJ3020 Antenna Placement(二分图最小路径覆盖)

一个矩形中，有N个城市’*’，现在这n个城市都要覆盖无线，若放置一个基站，那么它至多可以覆盖相邻的两个城市。问至少放置多少个基站才能使得所有的城市都覆盖无线？

这道题跟上一道题(HDU4185)几乎是一样的，我们依然先给城市进行编号，然后用它来建立二分图，因为是要把整个城市都覆盖完

所以这个题目求的是二分图的最小路径覆盖

const int N=1000+20;
int e[N][N],vis[N],match[N],n,m,num,temp[N][N];
char s[N][N];
int dfs(int u)
{
    for(int i=1; i<=num; i++)
    {
        if(e[u][i]&&!vis[i])
        {
            vis[i]=1;
            if(!match[i]||dfs(match[i]))
            {
                match[i]=u;
                return 1;
            }
        }
    }
    return 0;
}
int query()
{
    mem(match,0);
    int sum=0;
    for(int i=1; i<=num; i++)
    {
        mem(vis,0);
        if(dfs(i))sum++;
    }
    return sum;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        mem(temp,0);
        mem(e,0);
        num=0;
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            scanf("%s",s[i]+1);
            for(int j=1; j<=m; j++)
                if(s[i][j]=='*')
                    temp[i][j]=++num;
        }
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                if(s[i][j]=='*')
                {
                    if(i!=1&&s[i-1][j]=='*') e[temp[i][j]][temp[i-1][j]]=1;
                    if(j!=1&&s[i][j-1]=='*') e[temp[i][j]][temp[i][j-1]]=1;
                    if(i!=n&&s[i+1][j]=='*') e[temp[i][j]][temp[i+1][j]]=1;
                    if(j!=m&&s[i][j+1]=='*') e[temp[i][j]][temp[i][j+1]]=1;
                }
            }
        printf("%d\n",num-query()/2);
    }
    return 0;
}