861. 二分图的最大匹配
image.png
image.png
时间复杂度
没有任何一个点在多条边上，称为一个匹配。
虽然是无向图，但是存边存的是有向边，算法是只看左边的情况。所以只需要存左边指向右边就可以了。
image.png
算法流程：遍历每一个男生，然后每当枚举到一个新的男生，都要把妹子清空一遍，表示这些妹子我还没有考虑过（因为假如说有A B C D个妹子，虽然A妹子已经心有所属，那么她的st[A]就是true，但是她心有所属不代表这个新的男生就没机会了，这个新的男生害怕错过会努力尝试的。所以当遍历到一个新的男生，对于这个男生，要把所有妹子的状态改为false）。同时，对于每个男生，要保证每个妹子我只考虑一遍（因为我考虑这一遍，考虑了妹子有没有对象，有对象看看她对象有没有可能变心。如果妹子有对象且对象只爱她一个人，那么这个妹子就找到了自己的真爱，给祝福就可以了，不要纠缠人家了，找下一个吧。）。如果最后成功找到了自己的那个她，就 res ++。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 510, M = 100010;
int n1, n2, m;
vector<int> e[M];
int match[N]; // 每个妹子现在跟哪个男生在一块
bool st[N]; // 不要重复搜一个点
bool find(int boy)
{
for (auto girl : e[boy])
{
if (!st[girl])
{
st[girl] = true;
if (match[girl] == 0 || find(match[girl]))
{
match[girl] = boy;
return true;
}
}
}
return false;
}
int main()
{
cin >> n1 >> n2 >> m;
while (m -- )
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
}
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++;
}
cout << res << endl;
return 0;
}
