首页 > 代码库 > Bipartitegraph1469
Bipartitegraph1469
题目大意:有 p 个学生和 n 门课 , 每一个门课程可以被多个学生选(一个顶点可以被多条边连着),问能否满足:
1.每个学生选择一个不同的课程
2.每个课程都有不同的代表
上面两个条件即是二分匹配中每个顶点最多可以被一条边连着,求出能够满足条件最大的边,即为最大的顶点数目,与P数值比较即可。
题目要求找对课程的完全匹配,当对课程进行遍历。这里不能对学生进行遍历,因为可以允许部分学生没选课程(学生数大于课程数),但是每个课程必须都要被选
for(i=1;i<=p;i++) //p表示课程数目,这里不用能学生数目代替课程数目进行遍历
{
memset(use,false,sizeof(use));
if(!find(i))
{
printf("NO\n");
break;
}
}
if(i==p+1)
printf("YES\n");
Bipartitegraph1469
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。