当题目告诉你，这个图为二分图，而且左百部n 1 n1n1个点，右半部n 2 n2n2个点，下面m行，左半边点u与
右半边点v相连：
此时只需要一个有向图：
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N = 10000, M = 2e5 + 10; typedef long long ll; int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数 int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边 int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个 bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过 int m; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } bool find(int x) { for (int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; if (match[j] == 0 || find(match[j])) { match[j] = x; return true; } } } return false; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n1 >> n2 >> m; memset(h, -1, sizeof h); while (m--) { int a, b; cin >> a >> b; add(a, b); // add(b,a); } // 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点 int res = 0; for (int i = 1; i <= n1; i++) { memset(st, false, sizeof st); if (find(i)) res++; } cout << res << endl; return 0; }
而当他只告诉你这是个二分图时：模板
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N = 10000, M = 2e5 + 100; typedef long long ll; int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数 int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边 int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个 bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过 int m; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } bool find(int x) { for (int i = h[x]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; if (match[j] == 0 || find(match[j])) { match[j] = x; match[x]=j;//两点匹配好了 return true; } } } return false; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n1 >> n2 >> m; memset(h, -1, sizeof h); while (m--) { int a, b; cin >> a >> b; add(a, b+n1); add(b+n1,a); } // 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点 int res = 0; for (int i = 1; i <= n1+n2; i++) { if(!match[i]) { memset(st, false, sizeof st); if (find(i)) res++; } } cout << res << endl; return 0; }
进阶版：
每次还要重新构图，将上一次的匹配点，去掉。用c o l o r [ i ] [ j ] 记 颜 色 color[i][j]记颜色color[i][j]记颜色
代码：
#include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) typedef pair<int, int> PII; #define ll long long #define endl "\n" #define pb push_back const int N = 2005, M = 4005, INF = 0x3f3f3f3f; int h[N], ne[M], e[M], idx; int n, m; int match[N]; bool st[N]; int u[N]; int d[N];//统计度，答案为度最大的哪个点的度，而且从度最大的点开始染色 int v[N]; //不知道这个二分图的左右子图 ，一起用连无向边一起用染色法,只要点的标号不同无向边也可以，最后用邻接矩阵判定 int color[N][N]; int id[N]; void add(int a, int b) { ne[idx] = h[a], e[idx] = b, h[a] = idx++; } bool find(int x) { for (int i = h[x]; ~i; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = 1; if (match[j] == 0 || find(match[j])) { match[j] = x; match[x] = j; //不同之处 return true; } } } return false; } bool cmp(int a, int b) { return d[a] > d[b]; } void solve() { scanf("%d%d", &n, &m); int ans = 0; for (int i = 1; i <= m; i++) { scanf("%d%d", &u[i], &v[i]); d[u[i]]++; d[v[i]]++; ans = max(ans, max(d[u[i]], d[v[i]])); } for (int i = 1; i <= n; i++) id[i] = i; //初始化id for (int i = 1; i <= ans; i++) { memset(h, -1, sizeof(h)); //清空邻接表 idx = 0; for (int j = 1; j <= m; j++) { if (!color[u[j]][v[j]]) //每次取剩下没染色的建图 { add(u[j], v[j]); add(v[j], u[j]); } } for (int j = 1; j <= n; j++) match[j] = 0; sort(id + 1, id + 1 + n, cmp); //按度从大到小排列； //开始染色 for (int j = 1; j <= n; j++) { int p = id[j]; if (!match[p]) { for (int k = 1; k <= n; k++) st[k] = 0; find(p); } } for (int j = 1; j <= n; j++) { if (match[j]) { color[j][match[j]] = i, d[match[j]]--; //度-- } } } cout << ans << endl; for (int i = 1; i <= m; i++) { cout << color[v[i]][u[i]] << "\n"; } } int main() { ios::sync_with_stdio; cin.tie(0); cout.tie(0); int T = 1; //scanf("%d",&T); while (T--) { solve(); } return 0; }
