题意:在一个网格中有若干个点,每一次可以清除一行或者一列,问最少几次可以将网格中的点全部清除。
思路:这个题是一个入门的最大匹配题(这个好像不是思路..)。一般的方式就是将 行 看作集合A,列 看作集合B。
这么说有点抽象。举个例子:2行3列的矩阵可以看作是集合A={1,2}与B={1,2,3},假设矩阵[1][2] 存在点(别忘了题意),则A中的元素1与B中元素2连有一条边。
这样就可以将题给矩阵转化为二分图,再利用匈牙利算法得到最大匹配数就是答案了。
#include<iostream>
#include<cstring>
using namespace std;
int n, k;
int v1, v2;//二分图顶点集,都等于n
bool map[][];
bool visit[]; //记录v2中的每个点是否被搜索过
int link[]; //记录v2中的点y在v1中所匹配的点x的编号
int result;//最大匹配数
bool dfs(int x) {
for (int y = ; y <= v2; y++)
{
if (map[x][y] && !visit[y])
{
visit[y] = true;
if (link[y] == || dfs(link[y]))
{
link[y] = x;
return ;
}
}
}
return ;
} //匈牙利算法hungary algorithm
void search()
{
for (int x = ; x <= v1; x++)
{ memset(visit,false,sizeof(visit)); if (dfs(x)) //从v1中的节点x开始寻找增广路径p result++;
}
} int main()
{
cin >> n >> k;
v1 = v2 = n;
int x, y;
memset(map,,sizeof(map));
for (int i = ; i <= k; i++)
{
cin >> x >> y;
map[x][y] = true;
}
search();
cout << result << endl;
return ;
}