poj 3041 Asteroids 二分匹配 匈牙利算法 模板题

   
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=50000;
int max(int a,int b) {return a>b?a:b;};
int min(int a,int b) {return a<b?a:b;};
const int N = 500;
const int M=20000;
int n,m,x,y;
vector<int> G[1005];
int used[505],match[1005];
void add_edge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}
int dfs(int u)
{
    used[u]=1;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i],w=match[v];
        if(w<0||!used[w]&&dfs(w))
            {
                match[u]=v;
                match[v]=u;
                return 1;
            }
    }
    return 0;
}
int max_flow()
{
    memset(match,-1,sizeof(match));
    int ans=0;
    for(int u=1;u<=n;u++)
        if(match[u]<0)
        {
           memset(used,0,sizeof(used));
           if(dfs(u))
              ans++;
        }
    return ans;
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&x,&y);
            add_edge(x,y+n);
        }
        printf("%d\n",max_flow());
    }
    return 0;
}