求最大独立集,因为题意是男女之间关系,所以是二分图(也许那时还没有搞基吧……)这题就是最大独立集=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); } }
时间: 2024-12-03 18:16:36