HDU 1068 - Girls and Boys

求一个集合最多几个人,其之间任意两人没有暧昧关系。

二分图匹配

最大独立集 = 总点数 - 最大匹配数

匈牙利算法

因为每个同学都在二分图的两侧

当 A与B匹配时,B与A也匹配

所以 所求的最大匹配数要除以2

 #include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=;
int n,a,m,b;
vector<int>map[maxn];
int link[maxn];
int vis[maxn];
bool dfs(int t)
{
int size=map[t].size();
for(int i=;i<size;i++)
{
int x=map[t][i];
if(!vis[x])
{
vis[x]=;
if(link[x]==-||dfs(link[x]))
{
link[x]=t;
return ;
}
}
}
return ;
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=;i<n;i++)
{
scanf("%d: (%d)",&a,&m);
map[i].clear();
for(int j=;j<m;j++)
{
scanf("%d",&b);
map[a].push_back(b);
}
}
memset(link,-,sizeof(link));
int ans=;
for(int i=;i<n;i++)
{
memset(vis,,sizeof(vis));
if(dfs(i))
ans++;
}
printf("%d\n",n-ans/);
}
}
上一篇:HTML JSOgN to string


下一篇:好用的ssh工具oh-my-zsh / iterm2