POJ 3041 Asteroids（最小点覆盖）题解

题意：n*n的网格中有k个点，开一枪能摧毁一行或一列的所有点，问最少开几枪

思路：我们把网格看成两个集合，行集合和列集合，如果有点x，y那么就连接x->y，所以我们只要做最小点覆盖就好了。

参考：POJ3041-Asteroids

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn =  + ;

const int MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

int linker[maxn], n;

int g[maxn][maxn];

bool used[maxn];

bool dfs(int u){

    for(int v = ; v <= n; v++){

        if(g[u][v] && !used[v]){

            used[v] = true;

            if(linker[v] == - || dfs(linker[v])){

                linker[v] = u;

                return true;

            }

        }

    }

    return false;

}

int hungry(){

    int res = ;

    memset(linker, -, sizeof(linker));

    for(int u = ; u <= n; u++){

        memset(used, false, sizeof(used));

        if(dfs(u)) res++;

    }

    return res;

}

int main(){

    int k;

    while(~scanf("%d%d", &n, &k)){

        memset(g, , sizeof(g));

        for(int i = ; i <= k; i++){

            int x, y;

            scanf("%d%d", &x, &y);

            g[x][y] = ;

        }

        printf("%d\n", hungry());

    }

    return ;

}