本文主要是介绍poj 1469 COURSES 二分图匹配初识，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
poj 1469 COURSES
给定一些学生和一些课程，在给定这些课程有哪些学生能上，判断出是否能选出一些学生保证每个课程都有人上
解法：二分图匹配的匈牙利算法， 先把学生和课程关系用一个矩阵存下来，然后查找学生和课程可以连接的，把连上的课程标记出是哪个学生连接上的，然后继续查找，如果满足可以连接，可是课程已经被其他学生占用了，就查找那个占用的学生是否还可以连接到其他课程，知道结束。。
#include <stdio.h>
#include <string.h>int t;
int n, m;
int course;
int student;
int map[105][305];
int vis[305];
int zg[305];
int judge;
int i, j;int xi(int n)
{int i;for (i = 1; i <= m; i ++){if (map[n][i] && vis[i] == 0){vis[i] = 1;if (zg[i] == -1 || xi(zg[i])){zg[i] = n;return 1;}}}return 0;
}
int main()
{scanf("%d", &t);while (t --){int num = 0;judge = 0;memset(map, 0, sizeof(map));memset(vis, 0, sizeof(vis));memset(zg, 0, sizeof(zg));int i;scanf("%d%d", &n, &m);for (i = 0; i <= m; i ++)zg[i] = -1;for (i = 1; i <= n; i ++){scanf("%d", &course);if (course == 0)judge = 1;while (course --){scanf("%d", &student);map[i][student] = 1;}}if (judge)printf("NO\n");else{for (i = 1; i <= n; i ++){memset(vis, 0, sizeof(vis));if (xi(i))num ++;}if (num == n)printf("YES\n");elseprintf("NO\n");}}return 0;
}这篇关于poj 1469 COURSES 二分图匹配初识的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
