图论---匈牙利算法求二分图最大匹配的实现
开始编程前分析设计思路和程序的整体的框架，以及作为数学问题的性质：
程序流程图：
数学原理：
求解二分图最大匹配问题的算法，寻找一个边的子集，使得每个左部点都与右部点相连，并且没有两条边共享相同的端点。使用深度优先搜索来寻找增广路径。当找到一条增广路径时，将路径上的边加入匹配集合中，并更新匹配状态。重复这个过程直到无法找到增广路径为止。
时间复杂度分析：
时间消耗来自于DFS搜索和增广路径的寻找。对于每个左侧未匹配的点u，需要进行一次DFS搜索。在最坏情况下，DFS搜索需要遍历所有的右侧点，因此时间复杂度为O(n)。由于需要进行n次DFS搜索，所以时间复杂度为O(n^2)。
源代码：
#include <iostream> #include <vector> #include <cstring> using namespace std;const int MAXN = 505; // 最大顶点数 int n, m, k; // n为左部点数，m为右部点数,k为总变数 vector<int> G[MAXN]; // 邻接表表示二分图 int match[MAXN]; // match[i]表示右边第i个点匹配的是左边的哪点，如果没有匹配则为-1 bool vis[MAXN]; // DFS中标记右边各点是否已经被访问过 //进行深度搜索最大匹配边 bool dfs(int u) {int i;for (i = 0; i < G[u].size(); i++) {int v = G[u][i];if (!vis[v]) {vis[v] = true;if (match[v] == -1 || dfs(match[v])) {match[v] = u;//对边进行存储return true;}}}return false; } //匈牙利算法 int hungarian() {int res = 0;memset(match, -1, sizeof(match));for (int i = 1; i <= n; i++) {memset(vis, false, sizeof(vis));if (dfs(i)) res++;}return res; } int main() {cin >> n >> m >> k; // 输入左部点数和右部点数int u, v;int i=0;for(;i<k;i++){cin >> u >> v ; // 输入边 (u, v)，u属于左部，v属于右部G[u].push_back(v);}int max_matches = hungarian(); // 计算最大匹配数cout << "最大匹配边数：" << max_matches << endl;// 输出最大匹配数// 输出最大匹配的所有边cout << "最大匹配边为:" << endl;for (int v = 1; v <= m; v++) {if (match[v] != -1) { // 如果右部点v有匹配cout << "Edge: " << match[v] << " - " << v <<endl; // 输出匹配边}}system("pause");return 0; }
测试用例：（两侧顶点数均大于10，且两侧顶点数不相等）
输出结果：
