相关概念
- 二分图：如果一张无向图的 N(N>2) 个节点可以分成 A,B 两个非空集合，其中 A∩B=∅，并且在同一集合内的点之间都没有相连的边，那么称这张图为一张二分图。
- 匹配：
任意两端两条边都没有公共端点的边的集合称为图的一组匹配。
- 最大匹配：在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。
- 增广路：如果在二分图中存在一条连接两个非匹配的点的路径
path，使得非匹配边与匹配边在 path 上交替出现，那么称 path 是匹配 S 的增广路。
二分图匹配要素
- 节点能分成独立的两个集合，每个集合内有 0 条边；
- 每个节点只能和一条边进行匹配。
例题
题目
素数伴侣——华为机试题
题解
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 60010;
int n, a[N];
bool v[M], vis[N];
vector<int> g[N];
int match[N];
void init() {
v[1] = true;
for(int i = 2; i < M; i++) {
if(!v[i]) {
for(int j = 2 * i; j < M; j += i) v[j] = true;
}
}
}
bool dfs(int x) {
for(auto &y:g[x]) {
if(!vis[y]) {
vis[y] = true;
if(!match[y] || dfs(match[y])) {
match[y] = x;
return true;
}
}
}
return false;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
init();
for(int i = 1; i <= n; i++) {
if(a[i] & 1) continue;
for(int j = 1; j <= n; j++) {
if(a[j] & 1 && !v[a[i] + a[j]]) {
g[i].push_back(j);
}
}
}
int ans = 0;
for(int i = 1; i <= n; i ++) {
if((a[i] & 1) == 0) {
memset(vis, false, sizeof vis);
if(dfs(i)) ans++;
}
}
cout << ans << endl;
return 0;
}
