题目链接:
二分匹配的应用
求最大独立集
最大独立集等于=顶点数-匹配数
本体中由于男孩和女孩的学号是不分开的,所以匹配数应是求得的匹配数/2
代码:
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 500
int g[maxn][maxn];
int vis_x[maxn];
int vis_y[maxn];
int cx[maxn];
int cy[maxn];
int n;
int ans;
int path(int u)
{ vis_x[u]=;
for(int v=;v<n;v++)
{
if(vis_y[v]== && g[u][v]!=)
{
vis_y[v]=; if(cy[v]==- || path(cy[v]))
{
cx[u]=v;
cy[v]=u;
return ;
}
}
}
return ;
}
void MaxMatch()
{
memset(cx,-,sizeof(cx));
memset(cy,-,sizeof(cy)); for(int i=;i<n;i++)
{
if(cx[i]==-)
{ memset(vis_x,,sizeof(vis_x));
memset(vis_y,,sizeof(vis_y));
ans+=path(i);
}
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
int id;
int num;
char c;
ans=;
memset(g,,sizeof(g));
for(int i=;i<n;i++)
{
scanf("%d: (%d)", &id,&num);
for(int j=;j<num;j++)
{
int b;
scanf("%d",&b);
g[id][b]=;
}
}
MaxMatch();
cout<<n-ans/<<endl; }
return ;
}