POJ 3041 Asteroids 最小覆盖数

题目大意：

一辆宇宙飞船在一个小行星带中，你知道，这很危险。他有一种武器，可以清除掉一行或一列的小行星。问把小行星全部清除最少的武器使用次数。

思路：

因为每次可以清除掉一行或者一列，所以可以把行和列建成图，行和列为边，因为最后要全部清除，也就是说所有边都使用过，正好就是最小覆盖数。

最小覆盖数=最大匹配。

#include
  
   
#include
   
     const int MAXN=500+10; const int MAXM=10000+10; int head[MAXN],len,res[MAXN]; bool vis[MAXN]; struct edge { int to,next; }e[MAXM]; void add(int from,int to) { e[len].to=to; e[len].next=head[from]; head[from]=len++; } bool find(int a) { for(int i=head[a];i!=-1;i=e[i].next) { int id=e[i].to; if(!vis[id]) { vis[id]=true; if(res[id]==0 || find( res[id] )) { res[id]=a; return true; } } } return false; } int main() { int n,k; while(~scanf(%d%d,&n,&k)) { memset(res,0,sizeof(res)); memset(head,-1,sizeof(head)); len=0; for(int i=0;i