POJ-3041-Asteroids(二分图-最小点覆盖)

Asteroids

题意：

• 一种武器可以击败一行或一列中的所有东西，输出竟可能少的使用这种武器消灭所有东西

思路：

• 对于一个坐标为的东西，想消灭这个东西要么在行使用武器，或在列使用武器。只要采用这个坐标的其中一个维就可以将其消灭。
• 最小点覆盖就是用一个点集覆盖所有的边(只要边的一端在点集中就算覆盖这条边)
  于是就把原题拆分成二分图了，寻找二分图的最小点覆盖

最小点覆盖==最大边匹配

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
bool edge[550][550];
int match[550];
int vis[550];
int n;
int Hungarian(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]&&edge[x][i])
        {
            vis[i]=1;
            if(match[i]==-1||Hungarian(match[i]))
            {
                match[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main( )
{
    int k;
    int x,y;
    while(~scanf("%d%d",&n,&k))
    {
        memset(edge,false,sizeof(edge));
        memset(match,-1,sizeof(match));
        for(int i=1;i<=k;i++)
        {
            scanf("%d%d",&x,&y);
            edge[x][y]=true;
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(Hungarian(i))
            {
                ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}