题目大意:
给你p门课程和n个学生,一个学生可以选0门,1门,或者多门课程,现在要求一个由p个学生组成的集合,满足下列2个条件:
1.每个学生选择一个不同的课程
2.每个课程都有不同的代表
如果满足,就输出YES
题解:直接用二分图最大匹配即可,得到的匹配数如果等于课堂个数,则输出YES
#include<iostream> using namespace std; #define MAXSIZE 310 int map[MAXSIZE][MAXSIZE]; int vis[MAXSIZE];//是否拜访过 int isWho[MAXSIZE];//记录右边的点已经被左边哪个点占有 int dfs(int x ,int n) { int i; for(i=1;i<=n;i++)//遍历右边所有点 { if(!vis[i]&&map[x][i])//如果没有拜访过 并且有边存在 { vis[i]=1; if(isWho[i]==-1||dfs(isWho[i],n))//如果这个点现在还没人要 或者可以腾出位置 注意是dfs(isWho[i]) { isWho[i]=x; return 1; } } } return 0; } int main() { int num,n,p,i; //freopen("in.txt","r",stdin); scanf("%d",&num); while(num--) { memset(map,0,sizeof(map)); memset(isWho,-1,sizeof(isWho)); scanf("%d%d",&p,&n);//p代表 课堂个数 n代表学生个数 for(i=1;i<=p;i++) { int t; scanf("%d",&t); while(t--) { int t1; scanf("%d",&t1); map[i][t1]=1; } } int ans=0; for(i=1;i<=p;i++) { memset(vis,0,sizeof(vis)); if(dfs(i,n)) ans++; } printf("%s\n", ans == p ? "YES" : "NO"); } return 0; }
相关推荐
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
北大POJ初级-图算法 解题报告+AC代码
北大POJ3414-Pots 解题报告+AC代码
POJ3211--Washing Clothes
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
北大POJ1159-Palindrome 解题报告+AC代码
poj 1000-3000部分代码 网上收集
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
北大POJ3273-Monthly Expense POJ3273-Monthly Expense