二分图最大独立集模型

1.什么是二分图最大独立集

选出一些点是它们互不联通

2.如何求二分图最大独立集

最大独立集数=结点数-最小点覆盖数

因为最小点覆盖 满足 最小 和 连接所有边 ，所以 如果不选 最小点覆盖，那么所有点将不联同。因为最小点覆盖满足最小，所以用结点数-最小点覆盖 就是 最大 独立集。

不明白最小点覆盖戳这里

题目链接

题目大意：一个老师带他的一群学生去旅游。带走的这群学生整体必须满足给出四个条件之一。问最多能带走多少学生。

solution：如果不满足条件，就连一条边，然后求二分图最大独立集。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int N = 505;struct Ft{int h, s, b;
}M[N], F[N];int cnM, cnF;bool chk(Ft a, Ft b){if ( a.h-b.h > 40 || a.h-b.h < -40 ) return false;if ( a.s!=b.s ) return false;if ( a.b==b.b ) return false;return true;
}bool S[N], T[N];
int line[N], w[N][N];bool find(int x){S[x]=1;for ( int y=1; y<=cnF; y++ ){if ( !T[y] && w[x][y] ){T[y]=1;if ( !line[y] || find( line[y] ) ){line[y]=x;return true;}}}return false;
}int Hun(){int ans=0;memset( line,0,sizeof(line));for ( int i=1; i<=cnM; i++ ){memset(S,0,sizeof(S));memset(T,0,sizeof(T));if( find(i) ) ans++;}return cnF+cnM-ans; 
}map<string,int> mp1;
int tot;
int id(string str){if( mp1.count(str) ) return mp1[str];mp1[str]=++tot;return tot;
}
int main(){int T;scanf("%d", &T );while( T-- ){memset(w,0,sizeof(w));mp1.clear(); cnM=cnF=0;int n;scanf("%d", &n );for ( int i=1; i<=n; i++ ){int h;char x;string s, b;cin>>h>>x>>s>>b;if( x=='M' ){M[++cnM].h=h;M[cnM].s=id(s);M[cnM].b=id(b);}else {F[++cnF].h=h;F[cnF].s=id(s);F[cnF].b=id(b);}}for ( int i=1; i<=cnM; i++ )for ( int j=1; j<=cnF; j++ )if( chk(M[i], F[j]) ) w[i][j]=1;printf("%d\n", Hun() );}
}