Asteroids POJ - 3041

Asteroids POJ - 3041

　　题目大意：N*N的地图里，存在一些小行星，Bessie有个很牛x但又很耗蓝的武器，一次可以消灭一行或者一列的所有小行星，问最少使用多少次这个武器可以消灭所有的小行星？

　　第一次做这种建图的题，把每一行和每一列都视为一个点，然后给出的小行星坐标x,y就视为在x点和y点间连一条边，那么就是求最小点覆盖，而最小点覆盖=最大匹配（具体概念和证明之后再填坑），所以直接跑一遍匈牙利算法

 #include<cstdio>

 #include<cstring>

 #include<set>

 using namespace std;

 set<int> x[];//因为可能有重复的边，所以我用set

 int vis[],y[];

 int match(int u)

 {

     for(set<int>::iterator it=x[u].begin();it!=x[u].end();it++)

     {

         int v=*it;

         if(!vis[v])

         {

             vis[v]=;

             if(!y[v]||match(y[v]))

             {

                 y[v]=u;

                 return ;

             }

         }

     }

     return ;

 }

 int main()

 {

     int n,k,a,b;

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

     {

         for(int i=;i<=n;i++)

             x[i].clear();

         while(k--)

         {

             scanf("%d%d",&a,&b);

             x[a].insert(b);//对应的行和列连边

         }

         int ans=;

         memset(y,,sizeof(y));

         for(int i=;i<=n;i++)//求行列的最大匹配

         {

             memset(vis,,sizeof(vis));

             ans+=match(i);

         }

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

     }

     return ;

 }

点点边边变换无穷