【PTA数据结构 | C语言版】爱之匹配

本专栏持续输出数据结构题目集，欢迎订阅。

题目

在 520 这个日子里，没有比开发一个约会 App 更合适做的事情了。这个软件的需求很简单，用户输入自己的性别、想要约会的异性的年龄范围 [a,b]、身高范围 [c,d]，你要帮所有用户匹配出系统中满足其约会条件的异性。注意：双方性别、年龄、身高的要求必须全都符合对方的要求才可以；每人最多只能匹配一位异性。
当然，同时让每个人都满意的目标其实很难达到，你只要尽力配成最多对就可以了。

输入格式：
输入第 1 行给出正整数 n (≤500) ，为系统中登记的用户人数。随后 n 行，每行给出一位用户的信息，格式如下：

性别 年龄 身高 a b c d

其中 性别 为 0 表示女性，1 表示男性，是该用户自己的性别；年龄 和 身高 也是用户自己的信息，均为不超过 200 的正整数；后面四个数字依次表示该用户想要约会的异性的年龄下限、年龄上限、身高下限、身高上限 —— 注意这里的范围都是闭区间，数字均为不超过 200 的正整数。同行数字间以 1 个空格分隔。

输出格式：
在一行中输出能够同时成功配对的最大对数。

输入样例：
7
0 23 165 23 35 170 180
1 25 178 22 25 160 170
0 25 175 26 40 180 190
1 38 184 22 36 170 180
1 28 180 20 30 165 175
0 36 172 36 40 180 190
1 37 181 25 36 172 175

输出样例：
3

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_USERS 500// 用户信息结构体
typedef struct {int gender;       // 0:女性, 1:男性int age;          // 年龄int height;       // 身高int a, b;         // 期望异性年龄范围[a,b]int c, d;         // 期望异性身高范围[c,d]
} User;// 全局变量
User users[MAX_USERS];       // 存储所有用户信息
int graph[MAX_USERS][MAX_USERS];  // 二分图邻接矩阵
int match[MAX_USERS];        // 记录匹配关系
int visited[MAX_USERS];      // DFS访问标记
int n;                       // 用户总数// 检查两个用户是否互相满足条件
int isMatch(int u, int v) {// 检查性别是否为异性if (users[u].gender == users[v].gender) {return 0;}// u满足v的要求int u_ok = (users[u].age >= users[v].a) && (users[u].age <= users[v].b) &&(users[u].height >= users[v].c) && (users[u].height <= users[v].d);// v满足u的要求int v_ok = (users[v].age >= users[u].a) && (users[v].age <= users[u].b) &&(users[v].height >= users[u].c) && (users[v].height <= users[u].d);return u_ok && v_ok;
}// 匈牙利算法核心：DFS寻找增广路径
int dfs(int u) {// 遍历所有可能的异性用户for (int v = 0; v < n; v++) {// 如果u和v匹配，且v未被访问过if (graph[u][v] && !visited[v]) {visited[v] = 1;// 如果v未匹配，或v的匹配对象可以找到其他匹配if (match[v] == -1 || dfs(match[v])) {match[v] = u;return 1;}}}return 0;
}// 计算最大匹配数
int maxMatching() {int result = 0;memset(match, -1, sizeof(match));  // 初始化匹配关系为-1（未匹配）// 对每一位女性用户尝试匹配for (int u = 0; u < n; u++) {if (users[u].gender == 0) {  // 只处理女性作为左侧节点memset(visited, 0, sizeof(visited));if (dfs(u)) {result++;}}}return result;
}int main() {scanf("%d", &n);// 读取所有用户信息for (int i = 0; i < n; i++) {scanf("%d %d %d %d %d %d %d",&users[i].gender, &users[i].age, &users[i].height,&users[i].a, &users[i].b, &users[i].c, &users[i].d);}// 构建二分图：女性->男性的有向边memset(graph, 0, sizeof(graph));for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {// 只考虑女性对男性的匹配if (users[i].gender == 0 && users[j].gender == 1) {if (isMatch(i, j)) {graph[i][j] = 1;}}}}// 计算并输出最大匹配数printf("%d\n", maxMatching());return 0;
}