题意：给定一个Y行X列的网格，网格种有重要位置和障碍物。要求用最少的机器人看守所有重要的位置，每个机器人放在一个格子里，面朝上下左右四个方向之一发出激光直到射到障碍物为止，沿途都是看守范围。机器人不会阻挡射线。
“#”表示障碍物，“*”表示重要的位置，箭头表示最终机器人匹配的位置，求出机器人能够匹配出的最少位置个数。
分析：首先看题解是二分图匹配，但是建图目前还没想到呢。每个机器人绝对都在重要位置上，假设每个重要位置上都有机器人，可以保护哪几个重要物品。看是否能够匹配得来
#include<cstdio>
#include<memory.h>
#include <iostream>
using namespace std;
#define repu(i, a, b) for(int i = (a); i < (b); i++)
#define MAX 202
bool flag,visit[MAX]; ///记录V2中的某个点是否被搜索过
int match[MAX]; ///记录与V2中的点匹配的点的编号
int cow, stall; ///二分图中左边、右边集合中顶点的数目
int head[MAX];
struct edge
{
int to,next;
} e[];
int index,X,Y;
void addedge(int u,int v)
{
///向图中加边的算法，注意加上的是有向边
///u为v的后续节点既是v---->u
e[index].to=v;
e[index].next=head[u];
head[u]=index;
index++;
}
/// 匈牙利（邻接表）算法
bool dfs(int u)
{
int i,v;
for(i = head[u]; i != ; i = e[i].next)
{
v = e[i].to;
if(!visit[v]) ///如果节点v与u相邻并且未被查找过
{
visit[v] = true; ///标记v为已查找过
if(match[v] == - || dfs(match[v])) ///如果i未在前一个匹配M中，或者i在匹配M中，但是从与i相邻的节点出发可以有增广路径
{
match[v] = u; ///记录查找成功记录，更新匹配M（即“取反”）
return true; ///返回查找成功
}
}
}
return false;
}
int g[MAX][MAX];
pair<int, int> Map[MAX][MAX];
int n,m;
void MaxMatch()
{
int i,sum=;
memset(match,-,sizeof(match));
for(i = ; i < X; ++i)
{
memset(visit,false,sizeof(visit));///清空上次搜索时的标记
if(dfs(i)) ///从节点i尝试扩展
sum++;
}
printf("%d\n",sum);
}
void build()
{
int r = -, c = -;
repu(i,,n+)
{
bool flag = true;
repu(j,,m+)
{
if(g[i][j] == )
{
///如果没有障碍物，说明一个机器人就可以解决，否则就得加一个机器人
if(flag)
++r;
Map[i][j].first = r;
flag = false;
}
if(g[i][j] == )
flag = true;
}
}
repu(j,,m+)
{
bool flag = true;
repu(i,,n+)
{
if(g[i][j] == )
{
if(flag) ++c;
Map[i][j].second = c;
flag = false;
}
if(g[i][j] == ) flag = true;
}
}
X = r + ;
repu(i,,n+)
repu(j,,m+)
if(g[i][j] == )
{
addedge(Map[i][j].first,Map[i][j].second);
cout<<Map[i][j].first<<"--"<<Map[i][j].second<<endl;
}
}
void init()
{
int a, x, y;
memset(g, , sizeof(g));
scanf("%d%d%d", &n, &m, &a);
while(a--)
{
scanf("%d%d", &x, &y);
g[x][y] = ;
}
scanf("%d", &a);
while(a--)
{
scanf("%d%d", &x, &y);
g[x][y] = ;
}
}
///和POJ 3041的区别就是有障碍物
///因为有障碍物，所以需要进行行列拆分。。。即build
int main()
{
int T,a,b,x,y,l,r;
scanf("%d",&T);
while(T--)
{
memset(head,,sizeof(head)); ///切记要初始化
index = ;
init();
build();
MaxMatch();
}
return ;
}