题目描述
给定一个二分图，其左部点的个数为 \(n\)，右部点的个数为 \(m\)，边数为 \(e\)，求其最大匹配的边数。
左部点从 \(1\) 至 \(n\) 编号，右部点从 \(1\) 至 \(m\) 编号。
输入格式
输入的第一行是三个整数，分别代表 \(n\)，\(m\) 和 \(e\)。
接下来 \(e\) 行，每行两个整数 \(u, v\)，表示存在一条连接左部点 \(u\) 和右部点 \(v\) 的边。
输出格式
输出一行一个整数，代表二分图最大匹配的边数。
输入输出样例 #1
输入 #1
1 1 1
1 1
输出 #1
1
输入输出样例 #2
输入 #2
4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1
输出 #2
2
说明/提示
数据规模与约定
对于全部的测试点，保证：
- \(1 \leq n, m \leq 500\)。
- \(1 \leq e \leq 5 \times 10^4\)。
- \(1 \leq u \leq n\)，\(1 \leq v \leq m\)。
不保证给出的图没有重边。
思路
思路很简单，暴力的匹配每种可能，如果匹配的对象匹配过了，则回溯看匹配的对象的对象是否能匹配其他还没匹配过的对象，如果可行就更换对象，不过不可行，则继续遍历可以匹配的其他对象。
题解
时间复杂度 \(O(nm)\)
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,m,et;
int vis[N];
int match[N];
vector<int>e[N];
int ans = 0;bool dfs(int u)
{for(auto v:e[u]){if(vis[v]){continue;}vis[v]=true;if(!match[v]||dfs(match[v])){match[v] = u;return 1;}}return 0;
}void solve()
{cin>>n>>m>>et;for(int i=1;i<=et;i++){int u,v;cin>>u>>v;e[u].push_back(v);} for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(dfs(i))ans++;}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;// cin>>t;while(t--){solve();}return 0;
}