题意就是有一个地图,然后给你几个点的坐标标记为'x',然后你有一个武器,每次可以消灭一行或一列的'x',问最少需要几次能把所有的'x'消灭完。然后我们可以构建一个二分图,然后这就是一个最小覆盖集问题,最小覆盖数 = 最大匹配数,根据匈牙利算法就能求了。先上代码,以后再补详细的解释。
AC代码:
代码语言:javascript复制#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int b[10005];
int vis1[10005];
int vis[10005][10005];
int n,m,sum;
bool Find(int x){
for(int i=1;i<=n;i ){
if(vis[x][i] && !vis1[i]){
vis1[i] = 1;
if(b[i] == 0 || Find(b[i])){
b[i] = x;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i ){
int x,y;
cin>>x>>y;
vis[x][y] = 1;
}
sum = 0;
memset(b,0,sizeof(b));
for(int i=1;i<=n;i ){
memset(vis1,0,sizeof(vis1));
if(Find(i))sum ;
}
cout<<sum<<endl;
return 0;
}