图论算法：二分图最大匹配 对应蓝桥云课 代码框架见下
#include <iostream> #include <vector> #include <cstring> using namespace std; #define maxn 510 #define maxm 510 vector<int> adj[maxn]; //ad[i][j]代表i号左边的点的第j条边对应的右边的那个顶点 int pre[maxm]; //pre[i]代表和右边顶点i匹配的左边顶点编号 bool visit[maxm]; //visit[i]代表右边的顶点i是否产生了匹配 int n, m; //n代表左边点集数量，m代表右边点集数量 void Hungarian_Init(int n_, int m_) { n = n_ , m = m_ ; memset(pre, -1, sizeof(pre)); for (int i = 1; i <= n; ++i) { adj[i].clear(); } } void Hungarian_AddEdge(int u, int v) { adj[u].push_back(v); } bool Hungarian_findMatch(int u) { for (int i = 0; i < adj[u].size(); ++i) { int v = adj[u][i]; if (!visit[v]) { visit[v] = true; int vpre = pre[v]; pre[v] = u; if (vpre == -1 || Hungarian_findMatch(vpre)) { return true; } pre[v] = vpre; } } return false; } int Hungarian_GetMaxMatch() { int cnt = 0; for (int i = 1; i <= n; ++i) { memset(visit, false, sizeof(visit)); if (Hungarian_findMatch(i)) { cnt++; } } return cnt; } int main() { int n, m, k; cin >> n >> m >> k; Hungarian_Init(n, m); for (int i = 0; i < k; ++i) { int x, y; cin >> x >> y; Hungarian_AddEdge(x, y); } cout << Hungarian_GetMaxMatch() << endl; // 请在此输入您的代码 return 0; }代码练习1 对应蓝桥云课 职位匹配 代码见下
#include <iostream> #include <vector> #include <cstring> using namespace std; #define maxn 1010 #define maxm 1010 vector<int> adj[maxn]; //ad[i][j]代表i号左边的点的第j条边对应的右边的那个顶点 int pre[maxm]; //pre[i]代表和右边顶点i匹配的左边顶点编号 bool visit[maxm]; //visit[i]代表右边的顶点i是否产生了匹配 int n, m; //n代表左边点集数量，m代表右边点集数量 void Hungarian_Init(int n_, int m_) { n = n_ , m = m_ ; memset(pre, -1, sizeof(pre)); for (int i = 1; i <= n; ++i) { adj[i].clear(); } } void Hungarian_AddEdge(int u, int v) { adj[u].push_back(v); } bool Hungarian_findMatch(int u) { for (int i = 0; i < adj[u].size(); ++i) { int v = adj[u][i]; if (!visit[v]) { visit[v] = true; int vpre = pre[v]; pre[v] = u; if (vpre == -1 || Hungarian_findMatch(vpre)) { return true; } pre[v] = vpre; } } return false; } int Hungarian_GetMaxMatch() { int cnt = 0; for (int i = 1; i <= n; ++i) { memset(visit, false, sizeof(visit)); if (Hungarian_findMatch(i)) { cnt++; } } return cnt; } int main() { int n, m; //n: 职位数量 //m: 求职者数量 cin >> n >> m; Hungarian_Init(m, n); for(int i=1; i <= m; ++i){ int k; cin >> k; while(k--){ int x; cin >> x; Hungarian_AddEdge(i, x); } } cout << Hungarian_GetMaxMatch() << endl; return 0; }代码练习2 对应蓝桥云课 长方形的覆盖 代码见下
#include <iostream> #include <vector> #include <cstring> using namespace std; #define maxn 510 #define maxm 510 vector<int> adj[maxn]; //ad[i][j]代表i号左边的点的第j条边对应的右边的那个顶点 int pre[maxm]; //pre[i]代表和右边顶点i匹配的左边顶点编号 bool visit[maxm]; //visit[i]代表右边的顶点i是否产生了匹配 int n, m; //n代表左边点集数量，m代表右边点集数量 void Hungarian_Init(int n_, int m_) { n = n_, m = m_; memset(pre, -1, sizeof(pre)); for (int i = 1; i <= n; ++i) { adj[i].clear(); } } void Hungarian_AddEdge(int u, int v) { adj[u].push_back(v); } bool Hungarian_findMatch(int u) { for (int i = 0; i < adj[u].size(); ++i) { int v = adj[u][i]; if (!visit[v]) { visit[v] = true; int vpre = pre[v]; pre[v] = u; if (vpre == -1 || Hungarian_findMatch(vpre)) { return true; } pre[v] = vpre; } } return false; } int Hungarian_GetMaxMatch() { int cnt = 0; for (int i = 1; i <= n; ++i) { memset(visit, false, sizeof(visit)); if (Hungarian_findMatch(i)) { cnt++; } } return cnt; } char c[25][25]; int dir[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; int main() { int n; cin >> n; for (int i = 0; i < n; ++i) { cin >> c[i]; } Hungarian_Init(n * n, n * n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if ((i + j) & 1) { for (int k = 0; k < 4; ++k) { int di = i + dir[k][0]; int dj = j + dir[k][1]; if (dj < 0 || di == n || dj < 0 || dj == n) { continue; } if (c[i][j] == '1' || c[di][dj] == '1') { continue; } Hungarian_AddEdge(i * n + j + 1, di * n + dj + 1); } } } } cout << Hungarian_GetMaxMatch() << endl; return 0; }
