Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：求二分图最大匹配。
思路：匈牙利算法。
通过这三篇博客了解了相关概念，学习了匈牙利算法。 趣写算法系列之–匈牙利算法 二分图的最大匹配、完美匹配和匈牙利算法 匈牙利算法详解
感受就是：这个是相对容易学的算法。。并没有名字那么不明觉厉。。。
主体就是一个dfs的过程。。。。
不过据说有比较多的应用。
所以打算切一些题目加深理解以后再回来总结。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年05月25日 星期三 16时51分32秒
4File Name :code/hdu/2063.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E3+7;
34int n,m,k;
35int head[N];
36int link[N];
37bool vis[N];
38int cnt;
39int tot;
40struct Edge
41{
42 int to;
43 int nxt;
44}edge[N];
45void addedge( int u,int v)
46{
47 edge[cnt].to = v;
48 edge[cnt].nxt = head[u];
49 head[u] = cnt;
50 cnt++;
51}
52
53bool dfs(int u)
54{
55 // cout<<"u:"<<u<<endl;
56 for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt) //对于每个妹子，枚举她喜欢的蓝孩纸
57 {
58 int v = edge[i].to; //v为妹子u喜欢的蓝孩纸的编号
59 if (vis[v]) continue; //避免递归反复寻找同一个男孩子陷入死循环。
60 vis[v] = true;
61 if (link[v]==-1||dfs(link[v])) //如果这个男孩子是单身狗或者这个男孩子的女票还有其他男孩子可以选择（可以腾出位置）
62 {
63 link[v] = u ;// 男孩子v和女孩子u在一起了。
64 return true;
65 }
66 }
67 return false;
68}
69int hung(int n)
70{
71 int ans = 0 ;
72 ms(link,-1);
73 for ( int i = 1 ; i <= n ; i++) //扫描每个妹子
74 {
75 ms(vis,false);
76 if (dfs(i)) ans++;
77 }
78 return ans;
79}
80
81int main()
82{
83 #ifndef ONLINE_JUDGE
84 freopen("code/in.txt","r",stdin);
85 #endif
86
87
88 while (scanf("%d",&k)!=EOF)
89 {
90 if (k==0) break;
91 scanf("%d%d",&m,&n);
92 ms(head,-1);
93 cnt = 0 ;
94 for ( int i = 1 ; i <= k ; i++)
95 {
96 int u,v;
97 scanf("%d%d",&u,&v);
98 v = v + m; //调整编号，男生编号在女生之后。
99 addedge(u,v);
100 }
101 int ans = hung(m);
102 printf("%d\n",ans);
103 }
104
105 #ifndef ONLINE_JUDGE
106 fclose(stdin);
107 #endif
108 return 0;
109}