HDU-3020-Antenna Placement 二分图最小路径覆盖

二分图最小路径覆盖

题意:

给出一个n * m的矩形图,* 代表城市,o 代表空地,现有 4 种通讯仪器覆盖方式,覆盖当前点后(还可覆盖相邻的上下左右四个方向中的一个点),求:要想把所有城市都覆盖,最少需要多少仪器?

思路:

本来是暴力写的,遍历每个点,不知道为什么 WA ,后来才找到这个是最小路径覆盖

这个是比较好理解的:

  1. 首先遍历矩阵图,建图(注意是城市为顶点):遍历所有的城市,为其加上编号 id[ x ] [ y ]= ++ cnt (无向边);
  2. 再次遍历这个这个矩阵图,若两个城市相邻,那么我们就可以在这两个城市之间加一条可行边,边的顶点就是城市的编号
  3. 二分图模板:遍历每个顶点,判断是否可以找到与之匹配的另一半(即共享一个仪器)
  4. 得出有多少个点能找到另一半

答案含义:

n-ans/2 ==(n-ans)+(ans/2) /**没找到另一边的点(要自己用一个仪器)+ 找到另一半的点除以二 (即为边)*/

撸代码:

#include<stdio.h>
#include<string.h>
char e[50][20];
int id[50][20];
int h,m,n,w;
int line[500];
bool book[500];
bool edge[500][500];
int dir[4][2]= {0,1,1,0,0,-1,-1,0};
int work(int u)
{
    for(int i=1; i<=m; i++)
    {
        if(edge[u][i]&&!book[i])
        {
            book[i]=1;
            if(line[i]==-1||work(line[i]))
            {
                line[i]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int index=0;

        memset(id,0,sizeof(id));
        scanf("%d%d",&h,&w);
        for(int i=0; i<h; i++)
        {
            scanf("%s",e[i]);
            for(int j=0; j<w; j++)
            {
                if(e[i][j]=='*')
                    id[i][j]=++index;
            }
        }

        memset(edge,0,sizeof(edge));
        for(int i=0; i<h; i++)
        {
            for(int j=0; j<w; j++)
            {
                if(e[i][j]=='*')
                {
                    int tx,ty;
                    for(int k=0; k<4; k++)
                    {
                        tx=i+dir[k][0];
                        ty=j+dir[k][1];
                        if(tx>=0&&tx<h&&ty>=0&&ty<w)
                        {
                            if(e[tx][ty])
                                edge[id[i][j]][id[tx][ty]]=1;
                        }
                    }
                }
            }
        }
        n=m=index;
        memset(line,-1,sizeof(line));
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            memset(book,0,sizeof(book));
            ans+=work(i);
        }

        printf("%d\n",n-ans/2);

    }
    return 0;
}
上一篇:bootstrap 入门


下一篇:第33期宁波市小学生复赛题解(花式AC)