题目翻译

大二时，有人开始研究学生之间的恋爱关系。“恋爱关系”是指一个女孩和一个男孩之间的关系。出于研究的原因，有必要找出满足条件的最大集合:集合中没有两个学生“恋爱过”。程序的结果是这样一组学生的人数。

思路分析

要找出一个最大的集合，其中没有任何两个学生谈恋爱，那么我们只需要求出谈恋爱的对数，然后用总人数减去即可

#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

#define MAX 505
#define inf 0x3f3f3f3f
#define ll long long
#define p pair<ll, ll>

int n, fit[MAX][MAX], mat[MAX], vis[MAX];

bool match(int k) {
	for (int i = 0; i < n; i++) {
		if (fit[k][i] && !vis[i]) {
			vis[i] = 1;
			if (mat[i] == -1 || match(mat[i])) {
				mat[k] = i;
				mat[i] = k;
				return true;
			}
		}
	}
	return false;
}

int main() {
	while (cin >> n) {
		char s;
		memset(fit, 0, sizeof(fit));
		memset(mat, -1, sizeof(mat));
		for (int i = 0; i < n; i++) {
			ll a = 0, b;
			cin >> a;
			while (cin >> s)if (s == '(')break;
			cin >> b; cin >> s;
			for (int j = 0; j < b; j++) {
				ll c; cin >> c;
				fit[i][c] = 1;
			}
		}
		int ans = 0;
		for (int i = 0; i < n; i++) {
			memset(vis, 0, sizeof(vis));
			if (mat[i] != -1 || match(i))ans++;//i已经和之前的某个人匹配了
		}
		cout << n - ans / 2 << endl;
	}
}