PKU 3041 Asteroids 最小点覆盖(最大匹配模板题)

题目大意：给你一个N*N的矩阵， 里面有K个星球， 我们可以让武器攻击矩阵的一行或者一列来使得这个星球被击碎， 现在问你最少需要几个这种武器才能把所有的星球击碎？

解题思路：关键是建模构图

把每一行当成一个行节点(也当成一把武器,因为一把武器可以消灭一行)，构成集合1，每一列当成一个列节点(也当成一把武器,因为一把武器可以消灭一列)，构成集合2，则共有2*N(N个行节点,N个列节点,即2*N把武器)节点。若某行某列有一个障碍物，则该行节点和该列节点之间构成一条边。每一个障碍物的位置坐标将集合1与集合2中的点连接起来，也就是将每一个障碍物作为连接节点的边。假设1个行节点覆盖了5个列节点，即这个行节点与这5个列节点间有5条边（即五个障碍物），由于这5条边都被那个行节点覆盖，即表明这5个障碍物都在同一行上，于是可以一把武器全部清除。这样可以轻易的得出本题是一个最小点覆盖的问题。又有一个定理是：最小点覆盖数 = 最大匹配数，所以此题转化成求最大匹配数，有几把武器匹配成功，即需要射击几次，匹配成功的武器越多，射击的次数也就越少。

#include<iostream>

#include<cstring>

using namespace std;

bool vis[];

int n,k,x,y;

int graph[][],link[];

bool Find(int x)

{

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

          if(graph[x][i]&&!vis[i]){

              vis[i]=;//为了下一条语句中调用find做准备的，以免重复

              if(!link[i]||Find(link[i])){

                  link[i]=x;

                  return true;

              }

         }

    }

    return false;

}

int main()

{

    memset(link,,sizeof(link));

    memset(graph,,sizeof(graph));

    cin>>n>>k;

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

        cin>>x>>y;

        graph[x][y]=;

    }

    int ans=;

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

        memset(vis,,sizeof(vis));

        if(Find(i))

            ans++;

    }

    cout<<ans<<endl;

}