LA 3415

LA 3415

题目：.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1416

最大独立集 = 点数 - 最大匹配数

解法：按男女分类，不满足4条任何条件的建边，求最大匹配。

代码：

#include <stdio.h>
#include <ctime>
#include <math.h>
#include <limits.h>
#include <complex>
#include <string>
#include <functional>
#include <iterator>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <bitset>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <time.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>using namespace std;int n, n1, n2;
int p[510][510];
int book[510];
int match[510];
bool vis[510];bool dfs(int u)
{for (int i = 1; i <= n2; i++){if (book[i] == 0 && p[u][i] == 1){book[i] = 1;if (match[i] == 0 || dfs(match[i])){match[i] = u;return true;}}}return false;
}struct node
{char music[110];char sports[110];char sex[10];int high;
}stu[510],boy[510], girl[510];int main()
{int t;scanf("%d", &t);while (t--){memset(p, 0, sizeof(p));memset(match, 0, sizeof(match));memset(vis, false, sizeof(vis));n1 = 0, n2 = 0;scanf("%d", &n);for (int i = 1;i <= n;i++){scanf("%d%s%s%s", &stu[i].high, stu[i].sex, stu[i].music, stu[i].sports);if (stu[i].sex[0] == 'M'){n1++;boy[n1].high = stu[i].high;strcpy(boy[n1].music,stu[i].music);strcpy(boy[n1].sports, stu[i].sports);}else{n2++;girl[n2].high = stu[i].high;strcpy(girl[n2].music, stu[i].music);strcpy(girl[n2].sports, stu[i].sports);}}for (int i = 1;i <= n1;i++){for (int j = 1;j <= n2;j++){if (!(abs(boy[i].high - girl[j].high) > 40 || strcmp(boy[i].sports, girl[j].sports) == 0 || strcmp(boy[i].music, girl[j].music) != 0))p[i][j] = 1;}}int ans = 0;for (int i = 1; i <= n1; i++){memset(book, 0, sizeof(book));if (dfs(i))ans++;}printf("%dn", n - ans);}return 0;
}