Description

Input

Output

Sample Input

3 4
1 1
1 3
2 2
3 2

Sample Output

2


(匈牙利算法模板) 匈牙利算法是解决寻找二分图最大匹配的。
#include <iostream>
using namespace std;
#define N 510
int g[N][N],mark[N],link[N];
int n,x,y;
int dfs(int i)
{
    int j;
    for(j = 1;j<= y; j++)
    {
        if(g[i][j]&&!mark[j])            
        {
            
            mark[j] = 1;
            if(link[j]==-1||dfs(link[j]))
            {
                link[j] = i;               
                return 1;
            }
        }
    }
    return 0;                         
}   //完全是匈牙利算法模板。

int main()
{
    int i,sum = 0;
    int a,b;
    while(scanf("%d%d",&x,&n)!=EOF)
    {  y=x;
       memset(g,0,sizeof(g));
       sum=0;
       for(i=1;i<= n;i++)
       {
           scanf("%d%d",&a,&b);
           g[a][b]=1;
       }
       memset(link,-1,sizeof(link));   
       for(i = 1; i<=x; i++)
       {  
           memset(mark,0,sizeof(mark));  //最为重要的就是每次mark清零。
                                         //这么做是为了只保留link中对应匹配。
           if(dfs(i))   
               sum+=1;                   //找到增广路。
           
       }   
       printf("%d\n",sum);
    } 
    return 0;
} 
还是伟大的模板，搞了半天还不确定是不是明白了。

POJ 3041 Asteroids (匈牙利算法),布布扣,bubuko.com

POJ 3041 Asteroids (匈牙利算法)

原文：http://blog.csdn.net/qq2256420822/article/details/37659231