[poj3041]Asteroids(二分图的最小顶点覆盖)

题目大意：$N*N$的网格中有$n$颗行星，若每次可以消去一整行或一整列，求最小的攻击次数使得消去所有行星。

解题关键：将光束当做顶点，行星当做连接光束的边建图，题目转化为求该图的最小顶点覆盖，图的最小顶点覆盖是$NP$问题，又因为该图是二分图（水平方向的点和竖直方向的点），而二分图的最大匹配=最小顶点覆盖，即可求解该问题。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cmath>
#define maxn 20020
using namespace std;
typedef long long ll;
int n,m;
struct Edge{
    int nxt;
    int to;
    int w;
}e[maxn];
int head[maxn],cnt;
void add_edge(int u,int v){
    e[cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
}
int pre[maxn];
bool vis[maxn];
bool dfs(int u){
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(!vis[v]){
            vis[v]=true;
            if(pre[v]==-1||dfs(pre[v])){
                pre[v]=u;
                //pre[u]=v;
                return true;
            }
        }
    }
    return false;
}

int hungary(){
    int ans=0;
    memset(pre,-1,sizeof pre);
    for(int i=1;i<=2*n;i++){
        if(pre[i]==-1){
            memset(vis,0,sizeof vis);
            if(dfs(i)) ans++;
        }
    }
    return ans;
}
int a,b,k;

int main(){
    while(scanf("%d%d",&n,&k)!=EOF){
        memset(head, -1, sizeof head);
        cnt=0;
        for(int i=1;i<=k;i++){
            scanf("%d%d",&a,&b);
            add_edge(a,b+n);
        }
        printf("%d",hungary());
    }
    return 0;
}