POJ 2771 Guardian of Decency（二分图最大独立集，裸题）

二分图最大独立集，裸题
题目意思：
有k 个学生，学生有男女，某些男女之间有些可能谈恋爱。老师要带一些学生出去
旅游，要求不能有男女之间谈恋爱。
本题要点：
1、k <= 500, 用邻接矩阵来存图。
左部节点： n个男学生
右部节点： m个女学生。
2、老师要带尽可能多的学生出去，就是取的点尽量多，显然是二分图最大独立集。
二分图最大独立集 = 顶点个数 - 二分图最大匹配

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;
const int MaxN = 510, MaxLen = 110;
int a[MaxN][MaxN], match[MaxN];
bool vis[MaxN];
int T, n, m, k;struct stu
{
    int h;char sex[2], music[MaxLen], sport[MaxLen];
}boys[MaxN], girls[MaxN];bool dfs(int x)
{
    for(int y = 1; y <= m; ++y){
    if(!a[x][y] || vis[y])continue;vis[y] = true;if(!match[y] || dfs(match[y])){
    match[y] = x;return true;}}return false;
}void solve()
{
    for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= m; ++j){
    if(abs(boys[i].h - girls[j].h) > 40 || strcmp(boys[i].music, girls[j].music) != 0|| strcmp(boys[i].sport, girls[j].sport) == 0){
    a[i][j] = 0;		}else{
    a[i][j] = 1;}}}int ans = 0;for(int i = 1; i <= n; ++i){
    memset(vis, false, sizeof vis);if(dfs(i))++ans;}printf("%d\n", n + m - ans);
}int main()
{
    int height;char ch[2];scanf("%d", &T);while(T--){
    memset(a, 0, sizeof a);memset(match, 0, sizeof match);n = m = 0;scanf("%d", &k);while(k--){
    scanf("%d%s", &height, ch);	if(ch[0] == 'M'){
    boys[++n].h = height;strcpy(boys[n].sex, ch);scanf("%s%s", boys[n].music, boys[n].sport);}else{
    girls[++m].h = height;	strcpy(girls[m].sex, ch);scanf("%s%s", girls[m].music, girls[m].sport);}}solve();}return 0;
}/* 2 4 35 M classicism programming 0 M baroque skiing 43 M baroque chess 30 F baroque soccer 8 27 M romance programming 194 F baroque programming 67 M baroque ping-pong 51 M classicism programming 80 M classicism Paintball 35 M baroque ping-pong 39 F romance ping-pong 110 M romance Paintball *//* 3 7 */