题目大意
给定一个二分图，左部点集大小 n，右部点集大小 m，边集大小 e。求该二分图的最大匹配数（即最多的边数，使得这些边没有任何公共端点）。
AC代码
增广路的神奇之处在于，如果我们沿着一条增广路，将路径上的非匹配边变成匹配边，同时将匹配边变成非匹配边，那么匹配边的总数就会增加 1。
举个例子：
假设我们有下面这条增广路（实线代表匹配边，虚线代表非匹配边）：
未匹配点1 --(虚线)--> 点A ==(实线)== 点B --(虚线)--> 未匹配点2
-
这条路径从一个未匹配点开始，到一个未匹配点结束。
-
路径上的边是“非匹配-匹配-非匹配”交替的。
如果我们对它进行“增广”操作（虚实互换）：
未匹配点1 ==(实线)== 点A --(虚线)-- 点B ==(实线)== 未匹配点2
看！原来的 1 条匹配边（A-B）现在变成了 2 条（点1-A，B-点2）。匹配的总数增加了！
一个重要的结论是：一个匹配是最大匹配，当且仅当图中不存在增广路。 这也构成了匈牙利算法的理论基础。
视频教程
https://www.acwing.com/video/290/
匈牙利算法精髓：
👉 Note: 姑娘 j （connectedr）遇到新的追求者的心理活动：如果原来的男朋友有备胎，我就绿他，如果没有，那我看他太可怜了，就一直跟他在一起吧。
还有一个要注意的地方就是vis数组每次都要清空，因为实际上记的是这次寻找有没有找过这个宠物，这是为了防止死循环的发生（爆栈）
AC https://www.luogu.com.cn/record/183163854
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=510;
ll n,m,u,v,e,ans;
vector<ll> g[N],r[N];
bool vis[N];
ll matchr[N];
bool find(ll i) {
for(int j=0;j<g[i].size();j++) {
ll connectedr=g[i][j];
if(vis[connectedr])
continue;
vis[connectedr]=true;
if(matchr[connectedr]==0 || find(matchr[connectedr]) ) {
matchr[connectedr]=i;
return true;
}
}
return false;
}
int main()
{
cin>>n>>m>>e;
for(int i=1;i<=e;i++) {
cin>>u>>v;
g[u].push_back(v);
}
for(int i=1;i<=n;i++) {
fill(&vis[0],&vis[n+1],false);
if(find(i))
++ans;
}
cout<<ans<<endl;
return 0;
}
|
心路历程（WA，TLE，MLE……）
好像有点问题，但问题不大，过了70pts
https://www.luogu.com.cn/record/183070840
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=510;
ll n,m,u,v,e,ans;
vector<ll> l[N],r[N];
bool removeSame[N][N];
ll matchr[N],sl[N];
inline void Hungarian(){
for(int i=1;i<=n;i++) {
if(l[i].empty())
continue;
if(matchr[l[i][0]]==0) {
matchr[l[i][0]]=i;
++sl[i];++ans;
}else {
ll originMatch=matchr[l[i][0]];bool isBreak=false;
for(ll j=sl[originMatch];j<l[originMatch].size();j++) {
ll rConnected=l[originMatch][j];
if(matchr[rConnected]==0) {
matchr[rConnected]=originMatch;
sl[originMatch]=j+1;isBreak=true;
break;
}
}
if(isBreak) {
matchr[l[i][0]]=i;
++sl[i];
++ans;
}
}
}
}
int main()
{
cin>>n>>m>>e;
for(int i=1;i<=e;i++) {
cin>>u>>v;
l[u].push_back(v);
r[v].push_back(u);
}
Hungarian();
cout<<ans<<endl;
return 0;
}
|
80pts https://www.luogu.com.cn/record/183076675
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll N=510;
ll n,m,u,v,e,ans;
vector<ll> g[N],r[N];
bool removeSame[N][N];
ll matchr[N],sl[N];
inline void Hungarian(){
for(int i=1;i<=n;i++) {
if(g[i].empty())
continue;
if(matchr[g[i][0]]==0) {
matchr[g[i][0]]=i;
++sl[i];++ans;
}else {
for(int k=0;k<g[i].size();k++) {
ll originMatch=matchr[g[i][k]];bool isBreak=false;
for(ll j=sl[originMatch];j<g[originMatch].size();j++) {
ll rConnected=g[originMatch][j];
if(matchr[rConnected]==0) {
matchr[rConnected]=originMatch;
sl[originMatch]=j+1;isBreak=true;
break;
}
}
if(isBreak) {
matchr[g[i][0]]=i;
++sl[i];
++ans;
break;
}
}
}
}
}
int main()
{
cin>>n>>m>>e;
for(int i=1;i<=e;i++) {
cin>>u>>v;
g[u].push_back(v);
}
Hungarian();
cout<<ans<<endl;
return 0;
}
|
用循环是解决不了的，还是要递归。