#include <stdio.h>
#include <string.h>
#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define N 301
char weight[101][N]; /* weight[x][y] = 1 表示学生x可以做课程y的助教 */
char mat[N]; /* mat[y] = x,表示定点y和x匹配 */
char visit[N];
int nx, ny;
int find(int x)
{
int y;
debug("go to X.%d\n", x);
for (y = 1; y <= ny; y++) {
if (!visit[y] && weight[x][y] > 0) {
debug("go to Y.%d\n", y);
visit[y] = 1;
if (mat[y] == -1 || find(mat[y])) {
debug("%d %d %d\n", x, y, mat[y]);
/* 事实上程序实现的时候不用取反操作来标记哪些边已加入M,哪些边未加入M
* 因为由mat数组和visit数组就可以确定,若mat[y] != -1, 则(mat[y],y)必然是一条加入M的边
* 只要visit[y] = 0,则(x,y)必然是一条没有加入M的边
if (mat[y] != -1) {
weight[mat[y]][y] *= -1;
}
weight[x][y] *= -1;
*/
mat[y] = x;
return 1;
}
debug("return from Y.%d\n", y);
}
}
return 0;
}
int main()
{
int t, m, x, y, possible;
scanf("%d", &t);
while (t--) {
memset(weight, 0, sizeof(weight));
memset(mat, -1, sizeof(mat));
scanf("%d %d", &nx, &ny); /* X集合是课程,Y集合是学生, 课程应比学生少 */
for (x = 1; x <= nx; x++) {
scanf("%d", &m);
while (m--) {
scanf("%d", &y);
weight[x][y] = 1;
}
}
if (nx > ny) {
printf("NO\n"); continue;
}
possible = 1;
for (x = 1; x <= nx; x++) {
memset(visit, 0, sizeof(visit));
if (!find(x)) { /* X集合只要有一个定点找不到增广路径,则图必然不是完备匹配 */
possible = 0;
break;
}
debug("got an augmenting path...\n");
}
if (possible) {
printf("YES\n");
}
else {
printf("NO\n");
}
}
return 0;
}
分享到:
相关推荐
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
poj openjudge 1111题最大正向匹配 提交ac
poj1087贪心算法实验报告 poj1087贪心算法实验报告
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
POJ各题算法分类和题目推荐.pdf
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
供初学编程基本算法的人练习使用,在poj.grids.cn上
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
关于C++ 算法 北大网站POJ 八数码问题
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ中级-基本算法 解题报告+AC代码
acm.pku.edu.cn/OnlineJudge上一些已经通过的代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://128kj.iteye.com/blog/1705139