二分图匹配（匈牙利算法）

ios::sync_with_stdio(false); 的使用

https://blog.csdn.net/yujuan_mao/article/details/8119529

过山车

https://blog.csdn.net/mengxiang000000/article/details/52199146

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 /*
 5 测试数据 
 6 7
 7 1 1
 8 1 2
 9 2 2
10 2 3
11 3 1
12 3 2
13 4 3
14 答案 
15 3
16 */
17 /*匈牙利算法复杂度o(N3)*/ 
18 using namespace std;
19 const int maxn = 510;
20 int line[maxn][maxn];//邻接矩阵 
21 int used[maxn];// 
22 int nxt[maxn]; //如果匹配到的话匹配到的男生是谁
23 int t, n, m, u, v;
24 bool Find(int x){
25     //对于男生x能否有女生匹配 
26     for(int i = 1; i <= m; i++){
27         //第x个男生与第i个女生互相有好感
28         //并且与女生没有被匹配过 
29         if(line[x][i] && !used[i]){
30             used[i] = 1;
31              //i号女生如果没有被匹配则匹配该女生，如果该女生被匹配过，看能否将该女生匹配的男生匹配到其他女生上 
32             if(nxt[i] == 0 || Find(nxt[i])){ 
33                 nxt[i] = x;
34                 return true;
35             }
36         }
37     }
38     return false;
39 }
40 int match(){
41     int sum = 0;
42     //遍历每个男生，看能不能被匹配到 
43     for(int i = 0; i <= n; i++){
44         memset(used, 0, sizeof(used));
45         if(Find(i))sum++;
46     }
47     return sum;
48 } 
49 int main(){
50     ios::sync_with_stdio(false); 
51     int t;
52     cin >> t;
53     memset(nxt, 0, sizeof(nxt));
54     memset(line, 0, sizeof(line));
55     n = m = 4;
56     while(t--){
57         cin >> u >> v;
58         line[u][v] = 1;
59     }
60     cout << match() << endl;
61     return 0;
62 }

hdu过山车

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 /*
 5 测试数据 
 6 hdu2063
 7 */
 8 using namespace std;
 9 const int maxn = 510;
10 int line[maxn][maxn];//邻接矩阵 
11 int used[maxn];//如果匹配到的话匹配到的男生是谁 
12 int nxt[maxn]; //
13 int t, n, m, u, v;
14 bool Find(int x){
15     //对于男生x能否有女生匹配 
16     for(int i = 1; i <= m; i++){
17         //第x个男生与第i个女生互相有好感
18         //并且女生没有被匹配过 
19         if(line[x][i] && !used[i]){
20             used[i] = 1;
21             if(nxt[i] == 0 || Find(nxt[i])){
22                 nxt[i] = x;
23                 return true;
24             }
25         }
26     }
27     return false;
28 }
29 int match(){
30     int sum = 0;
31     //遍历每个男生，看能不能被匹配到 
32     for(int i = 0; i <= n; i++){
33         memset(used, 0, sizeof(used));
34         if(Find(i))sum++;
35     }
36     return sum;
37 } 
38 int main(){
39     ios::sync_with_stdio(false); 
40     int k;
41     while(cin >> k && k){
42         cin >> n >> m;
43         memset(line, 0, sizeof(line));
44         memset(nxt, 0, sizeof(nxt));
45         while(k--){
46             cin >> u >> v;
47             line[u][v] = 1;
48         }
49     }
50     cout << match() << endl;
51     return 0;
52 }