题目类型 最大独立集
题目意思
给出 n 个学生的信息 其中只要两个学生满足以下条件之一就可以一起出行:
1.身高差超过 40
2.性别不同
3.喜欢音乐类型不同
4.喜欢体育类型相同
问最多有多少个学生可以一起出行
解题方法
依照性别不同构建二分图 (即男的一个集合 女的一个集合)
则最大独立集 = 总点数 - 二分最大匹配数
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 500 + 10;
struct P {
int a;
char s[3][110];
}p[maxn];
bool g[maxn][maxn];
int y[maxn];
bool vis[maxn];
int abs(int x) {
return x < 0 ? -x : x;
}
bool dfs(int u, int n) {
for( int i=0; i<n; i++ ) {
if(g[u][i] && vis[i] == false) {
vis[i] = true;
if(y[i] == -1 || dfs(y[i], n)) {
y[i] = u;
return true;
}
}
}
return false;
}
int main() {
freopen("in", "r", stdin);
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
for( int i=0; i<n; i++ ) {
scanf("%d%s%s%s", &p[i].a, p[i].s[0], p[i].s[1], p[i].s[2]);
}
memset(g, 0, sizeof(g));
memset(y, -1, sizeof(y));
for( int i=0; i<n; i++ ) {
for( int j=i+1; j<n; j++ ) {
if(abs(p[i].a-p[j].a)<=40 && p[i].s[0][0] != p[j].s[0][0] && strcmp(p[i].s[1], p[j].s[1]) == 0 && strcmp(p[i].s[2],
p[j].s[2])) {
g[i][j] = g[j][i] = true;
}
}
}
int ans = 0;
for( int i=0; i<n; i++ ) {
memset(vis, 0, sizeof(vis));
if(dfs(i, n)) ans++;
}
printf("%d\n", n - ans/2);//由于是不分男女建图 所以求出的最大匹配/2才是原来的分男女建图的二分最大匹配数
}
return 0;
}