二分图最大匹配

就是说左边一大堆，右边一大堆。然后呢，做连线，连到最多的就是最大匹配。方法就是，先弄一条匹配，然后加两条不匹配，这样就形成了A-B=C-D其中=是匹配，那么换成A=B-C=D不就是匹配两个了吗，然后继续加线条一直加上，就可以得到最大匹配。在这个具体写法呢，就是便利每一个左边的点，然后每次便利的时候清理visited,如果已经被匹配过的，给他找个其他匹配的，这样就腾出了位置，也就多了个线条，那么就多了个匹配。那么返回true,并且result++。
具体的代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;vector<vector<int>> adj;
vector<int> visited;
vector<int> match;bool dfs(int u){//对左边能连到右边的都遍历，每访问过的访问，当匹配0或者能找到其他新匹配就把他匹配到我，那就是多了个匹配，因为他匹配了其他的for(int x: adj[u]){if(!visited[x]){visited[x] = true;if(match[x] == 0||dfs(match[x])){match[x] = u;return true;}}}return false;
}int main()
{int n1, n2, m;cin >> n1 >> n2 >> m;adj.resize(n1+1);match.resize(n2+1);visited.resize(n2+1);int a, b;while (m -- ){cin >> a >> b;adj[a].push_back(b);}for (int i = 0; i <= n2; i ++ ){match[i] = 0;visited[i] = 0;}int result = 0;for (int i = 1; i <= n1; i ++ ){//便利每一个，如果有就++，每次dfs之前要重置访问标记，不然就完了for(int j = 1; j<=n2; j++) visited[j] = false;if(dfs(i)){result++;}}cout << result;return 0;
}