http://poj.org/problem?id=3041
这个题目真的一点变形都没有，直接套一个匈牙利算法求最大匹配数。把所给的点，分成两个集合，然后用一个模板就可以了
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 using namespace std;
5 #define N 510
6 int map[N][N],v[N],m[N];
7 int n,g;
8 bool dfs(int x)
9 {
10 int i;
11 for(i=1;i<=n;i++)
12 {
13 if(!v[i]&&map[x][i])
14 {
15 v[i]=1;
16 if(m[i]==-1||dfs(m[i]))
17 {
18 m[i]=x;
19 return true;
20 }
21 }
22 }
23 return false;
24 }
25 int find()
26 {
27 int i;
28 int count=0;
29 for(i=1;i<=n;i++)
30 {
31 memset(v,0,sizeof(v));
32 if(dfs(i)) count++;
33 }
34 return count;
35 }
36 int main()
37 {
38 int i;
39 while(cin>>n>>g)
40 {
41 int x,y;
42 memset(map,0,sizeof(map));
43 memset(m,-1,sizeof(m));
44 for(i=1;i<=g;i++)
45 {
46 cin>>x>>y;
47 map[x][y]=1;
48 }
49 int ans=find();
50 cout<<ans<<endl;
51 }
52 return 0;
53 }