Girls and Boys
题意:有人想对学校里面的男女学生做暧昧关系做研究,要将没有暧昧关系的学生分到同一个组里面,问一个组最大人数是多少。
分析:每两个节点之间都不相邻,也就是求二分图最大点独立数。在没有孤立点的二分图里,最大点独立数=n-最大匹配数。
View Code
1 #include2 #include 3 using namespace std; 4 vector vex[500],group; 5 int n,m,max_match,sum,mat[500],set[500],counter; 6 bool visited[500],over[500]; 7 int path(int u) 8 { 9 int i,v;10 for(i=0;i