二分图最小路径覆盖
题意：
给出一个n * m的矩形图，* 代表城市，o 代表空地，现有 4 种通讯仪器覆盖方式，覆盖当前点后（还可覆盖相邻的上下左右四个方向中的一个点），求：要想把所有城市都覆盖，最少需要多少仪器？
思路：
本来是暴力写的，遍历每个点，不知道为什么 WA ，后来才找到这个是最小路径覆盖
这个是比较好理解的：
- 首先遍历矩阵图，建图（注意是城市为顶点）：遍历所有的城市，为其加上编号 id[ x ] [ y ]= ++ cnt （无向边）;
- 再次遍历这个这个矩阵图，若两个城市相邻，那么我们就可以在这两个城市之间加一条可行边，边的顶点就是城市的编号
- 二分图模板：遍历每个顶点，判断是否可以找到与之匹配的另一半（即共享一个仪器）
- 得出有多少个点能找到另一半
答案含义：
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-ans/2);
}
return 0;
}