POJ-3020-Antenna Placement(二分图-最

Antenna Placement

题意：

• 一个天线可以覆盖距离它为一的上下左右四个方向。但是每个天线只能选择四个方向的一个进行覆盖。然后给出一些点，这是要输出最小的天线数量覆盖这些给出的点

思路：

• 每个节点只能与一个节点共用一个天线，两个节点有一条线。那就成了最小边覆盖所有的节点了
• 注意：因为每个节点的上下左右都可以共用一个天线，所以节点与节点之间是双向边。于是求出的最大匹配是单向匹配的两倍

最小边覆盖==总点数-最大边匹配

思考：

• 我只向右和下遍历，各个点之间连接的边就是单向边了，然后求出来的最大匹配不就是所求的吗？但是答案错误。我想了想。其实我们用单向边图中的点都用了两次。因为在建图遍历时，每个点都在起点集合也在终点集合所以应该双向建图。而且建图的总点数应该是两倍的节点总数
  最小边覆盖==(建图总点数-建图的最大边匹配)/2

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<int>vep[500];
int cnt;
char s;
int mark[45][15];
int vis[500];
int match[500];
int n,m;
void init( )
{
    for(int i=0;i<=500;i++)
    {
        vep[i].clear( );
    }
}
int Hungarian(int x)
{
    for(int i=0;i<vep[x].size( );i++)
    {
        int v=vep[x][i];
        if(!vis[v])
        {
            vis[v]=1;
            if(match[v]==-1||Hungarian(match[v]))
            {
                match[v]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main( )
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        cnt=0;
        memset(mark,0,sizeof(mark));
        memset(match,-1,sizeof(match));
        init( );
        scanf("%d%d",&n,&m);
        getchar( );
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%c",&s);
                if(s=='*')
                {
                    cnt++;
                    mark[i][j]=cnt;//给节点编号
                }
            }
            getchar( );
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(mark[i][j+1]&&mark[i][j])//mark[i][j]节点可以与mark[i][j+1]共用一条天线，意味着两节点有一条边
                {
                    vep[mark[i][j]].push_back(mark[i][j+1]);
                }
                if(mark[i+1][j]&&mark[i][j])
                {
                    vep[mark[i][j]].push_back(mark[i+1][j]);
                }
                if(mark[i][j]&&mark[i-1][j])
                {
                    vep[mark[i][j]].push_back(mark[i-1][j]);
                }
                if(mark[i][j]&&mark[i][j-1])
                {
                    vep[mark[i][j]].push_back(mark[i][j-1]);
                }
            }
        }
        int ans=0;
        for(int i=1;i<=cnt;i++)
        {
            memset(vis,0,sizeof(vis));
            if(Hungarian(i))
            {
                ans++;
            }
        }
        printf("%d\n",cnt-ans/2);
    }
    return 0;
}