题意:在N*N的格子中,有一些小行星,bessie有一把枪,能一次消灭一行或一列的行星,求最少需要多少子弹
思路:是求最小点覆盖 = 最大匹配 所以转换成求最大匹配
#include <stdio.h>
#include <string.h>
#define M 505
int map[M][M],xM[M],yM[M],vis[M];
int n;
int dfs (int u)
{
int v;
for (v = 1;v
<= n;v ++)
if (map[u][v]&&!vis[v])
{
vis[v] = 1;
if (yM[v] == -1||dfs(yM[v]))
{
yM[v] = u;
......
阅读全文