POJ 3020 Antenna Placement(二分图的最大匹配)

POJ 3020 Antenna Placement(二分图的最大匹配)

http://blog.csdn.net/lyy289065406/article/details/6647040

题意:

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

问至少放置多少个基站才能使得所有的城市都覆盖无线？这个基站的位置可以任意放,不管当前位置是’*’还是’o’.

分析:

一直就感觉这道题很相似,跟以前做的网格用1*2小矩阵覆盖的题目类似.

首先本题既不是二分图的最小边覆盖,也不是DAG最小路径覆盖问题,只不过是二分图的最大匹配问题而已.

我们把图中的每个’*’都标号,分别放到二分图的左右点集去.(行号+列号==偶数的放左边, 行号+列号==奇数的放右边). 如果存在两个相邻的’*’,那么就在他们之间连一条无向边(这条边肯定是连接左右点集的,因为网格是天然二分的). 这样就行了一个新的二分图G.

首先我们要知道对于任意一个’*’来说,它或者由一个基站(1*2矩形)单独覆盖(即该矩形实际只能算覆盖了1个’*’),或者由一个基站通过覆盖另一个与其相邻的’*’来顺便把它覆盖(即该矩形有效覆盖了2个相邻的’*’).

既然总的’*’是固定的,我们想要用基站的数目最少,必须使得实际有效覆盖两个’*’的基站数目最多(想想对不对).那么实际有效覆盖两个’*’的基站数目最多有多少个呢? 这个数目正好等于我们所建二分图的最大匹配边数.(因为二分图的每条匹配边就是一条正好有效覆盖两个相邻’*’的矩形). 既然这样 我们最终需要的基站总数= ‘*’的总数-最大匹配边数(因为每条匹配边正好覆盖了2个’*’)

AC代码:

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=500;

struct Max_Match
{
    int n,m;
    vector<int> g[maxn];
    bool vis[maxn];
    int left[maxn];

    void init(int n,int m)
    {
        this->n=n;
        this->m=m;
        for(int i=1;i<=n;i++) g[i].clear();
        memset(left,-1,sizeof(left));
    }

    bool match(int u)
    {
        for(int i=0; i<g[u].size(); ++i)
        {
            int v=g[u][i];
            if(!vis[v])
            {
                vis[v]=true;
                if(left[v]==-1 || match(left[v]))
                {
                    left[v]=u;
                    return true;
                }
            }
        }
        return false;
    }

    int solve()
    {
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(match(i)) ans++;
        }
        return ans;
    }
}MM;

struct Node
{
    int x,y;
    Node(){}
    Node(int x,int y):x(x),y(y){}
    bool link(Node& rhs)
    {
        if(x==rhs.x && y+1==rhs.y) return true;
        if(x==rhs.x && y-1==rhs.y) return true;
        if(x+1==rhs.x && y==rhs.y) return true;
        if(x-1==rhs.x && y==rhs.y) return true;
        return false;
    }
}node1[maxn],node2[maxn];

int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        int R,C;
        scanf("%d%d",&R,&C);
        int num1=0, num2=0;
        for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++)
        {
            char c;
            scanf(" %c",&c);
            if(c=='*')
            {
                if( (i+j)%2==0 ) node1[++num1]=Node(i,j);
                else node2[++num2]=Node(i,j);
            }
        }

        MM.init(num1,num2);
        for(int i=1;i<=num1;++i)
        for(int j=1;j<=num2;++j)
        {
            if(node1[i].link(node2[j]))
                MM.g[i].push_back(j);
        }

        printf("%d\n",num1+num2-MM.solve());
    }
    return 0;
}