该题题义为给定网格的中的点的坐标，现在要去将这些点摧毁，有一种武器能够一次摧毁一行或者是一列的所有目标，问最少用多少次该武器能够使得所有的目标消失。
这题怎么转化为二分图去做呢，过程是这样的，首先对于每个目标有两种方式能够让其消失，一种是在其所在行上使用武器，一种是在其所在列上使用武器。那么对于所有的目标而言，只要在行列满足之一的地方使用武器就可以全部清除目标。于是我们可以将目标所在行列进行匹配，然后再求最小顶点覆盖就可以了。因为最小顶点覆盖就是满足一条边至少有一个顶点在这个顶点集中。
代码如下:
#include#include #include #include #define MAXN 1000using namespace std;int N, M, match[MAXN], visit[MAXN];int G[MAXN][MAXN];bool path(int u){ // visit[u] = 1; // 上式是错的，visit所使用的对象是与u对应的部分，所以不能在这一标记 for (int i = 1; i <= N; ++i) { if (!G[u][i] || visit[i]) { continue; } visit[i] = 1; // 考虑应该是y部的访问情况 if (!match[i] || path(match[i])) { match[i] = u; return true; } } return false;}int main(){ int x, y, ans = 0; scanf("%d %d", &N, &M); for (int i = 1; i <= M; ++i) { scanf("%d %d", &x, &y); G[x][y] = 1; } for (int i = 1; i <= N; ++i) { memset(visit, 0, sizeof (visit)); if (path(i)) { ++ans; } } printf("%d\n", ans); return 0; }