首页 > 代码库 > Bipartitegraph1469

Bipartitegraph1469

题目大意:有 个学生和 门课 , 每一个门课程可以被多个学生选(一个顶点可以被多条边连着),问能否满足: 

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