974
hdu 1068 Girls and Boys
求最大獨立集，因為題意是男女之間關係，所以是二分圖（也許那時還沒有搞基吧……）這題就是最大獨立集=n-（最大覆蓋集=最大匹配）
和hdu1054幾乎一模一樣
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#define INF 1E9
using namespace std;
vector<int> m[500];
int pre[500],n;
bool vis[500];
bool dfs(int v)
{
int u;
for(int i=0;i<m[v].size();i++)
{
u=m[v][i];
if(vis[u])continue;
vis[u]=1;
if(pre[u]!=-1&&!dfs(pre[u]))continue;
pre[u]=v;
return 1;
}
return 0;
}
int KM()
{
memset(pre,-1,sizeof(pre));
int ans=0;
for(int i=0;i<n;i++)
{
memset(vis,0,sizeof(vis));
vis[i]=1;
ans+=dfs(i);
}
return ans;
}
int main()
{
while(~scanf("%d",&n))
{
int i,j,num,v,u;
for(i=0;i<n;i++)m[i].clear();
for(i=0;i<n;i++)
{
scanf("%d%*c%*c%*c%d%*c",&v,&num);
for(j=0;j<num;j++)
{
scanf("%d",&u);
m[v].push_back(u);
m[u].push_back(v);
}
}
printf("%d\n",n-KM()/2);
}
}
最後更新：2017-04-02 22:15:46