Hdu_2063 过山车 -最大匹配（邻接表版）

题目：就是最大匹配了

/************************************************
Author        :DarkTong
Created Time  :2016/8/1 12:53:27
File Name     :Hdu2063.cpp
*************************************************/#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 500 + 10;
vector<int> w[maxn];
int n, m;
int Left[maxn];
bool used[maxn];
bool match(int i)
{for(int j=0;j<w[i].size();++j) if(!used[w[i][j]]){int v = w[i][j];used[v] = true;if(!Left[v]||match(Left[v])){Left[v] = i;return true;}}return false;
}
//返回最大匹配数
int hungary()
{int res=0;memset(Left, 0, sizeof(Left));for(int i=1;i<=m;++i){memset(used, 0, sizeof(used));if(match(i)) res++;}return res;
}int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int k;while(scanf("%d", &k)==1&&k){for(int i=0;i<maxn;++i) w[i].clear();int u, v;scanf("%d%d", &m, &n);for(int i=1;i<=k;++i){scanf("%d%d", &u, &v);w[u].push_back(v);}printf("%d\n", hungary());}return 0;
}