nyoj 月老的难题 (稳定婚姻问题)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<string>
 6 #include<queue>
 7 #include<algorithm>
 8 #include<map>
 9 #include<iomanip>
10 #include<climits>
11 #include<string.h>
12 #include<cmath>
13 #include<stdlib.h>
14 #include<vector>
15 #include<set>
16 #define INF 1e7
17 #define MAXN 100010
18 #define maxn 50
19 #define maxm 1000
20 #define Mod 1000007
21 using namespace std;
22 typedef long long LL;
23 
24 
25 int T;
26 int u, v;
27 int n, m;
28 int ans;
29 vector<int> G[555];
30 int vis[10010];
31 int match[10010];
32 
33 bool path(int u)
34 {
35     for (int i = 0; i < G[u].size(); ++i) {
36         int v = G[u][i];
37         if (true == vis[v]) continue;
38         vis[v] = true;
39         if (match[v] == -1 || path(match[v])) {
40             match[v] = u;
41             return true;
42         }
43     }
44     return false;
45 }
46 
47 void hungarian()
48 {
49     ans = 0;
50     memset(match,-1,sizeof(match));
51     for (int i = 1; i <= n; ++i) {
52         memset(vis,0,sizeof(vis));
53         if (path(i)) ans++;
54     }
55 }
56 
57 void run()
58 {
59     scanf("%d%d",&n,&m);
60     for (int i = 0; i <= n; ++i) {
61         G[i].clear();
62     }
63     for (int i = 0; i < m; ++i) {
64         scanf("%d%d",&u,&v);
65         G[u].push_back(v);
66     }
67     hungarian();
68     printf("%d\n",ans);
69     
70 }
71 int main()
72 {
73     scanf("%d", &T);
74     while (T--)
75         run();
76     return 0;
77 }