HDU - 1068 Girls and Boys（二分匹配，最大独立集）

HDU - 1068 Girls and Boys

POJ - 1466 Girls and Boys

本题数据N的规模应该在（n<500）
$1<=N<=500$
$最大独立集=节点数?（减号）最大匹配数$
本题还要注意的一点是 mat[from][to]=mat[to][from]=1只有这样并将结果除以二，才能得到正确结果。这是因为比如说1与2有关系与2与1有关系相同，只有都赋值为1并除以二才能得到最大匹配的正确结果。

#include<cstdio>
#include<cstring>
const int N = 510;
int match[N][N],vis[N],pre[N];
int n;
int dfs(int x)
{
    for(int i=1;i<=n;i++){
    if(!vis[i]&&match[x][i]){
    vis[i]=1;if(pre[i]==-1||dfs(pre[i])){
    pre[i]=x;return 1;}}}return 0;
}
int Maxmatch()
{
    memset(pre,-1,sizeof pre);int ans=0;for(int i=1;i<=n;i++){
    memset(vis,0,sizeof vis);ans+=dfs(i);}return ans;
}
int main()
{
    while(scanf("%d",&n)!=EOF){
    memset(match,0,sizeof match);for(int i=1,m,a,b;i<=n;i++){
    scanf("%d: (%d)",&a,&m);a++;while(m--){
    scanf("%d",&b);b++;match[a][b]=match[b][a]=1;}}printf("%d\n",n-Maxmatch()/2);}return 0;
}