题意:在给出的学生里求出最大的数m,使得m中任意两个学生都不存在romantically involved(有关系),也就是求这个二分图的最大独立集,这个题的最大独立集等于N-最大匹配/2。因为在建图的时候人数扩大了一倍。
#include<iostream> using namespace std; bool g[505][505],vis[505]; int link[505]; int n; bool dfs(int u) { int v; for(v=0;v<n;v++) if(g[u][v]&&!vis[v]) { vis[v]=1; if(link[v]==-1||dfs(link[v])) { link[v]=u; return true; } } return false; } int maxmatch() { int u,num=0; memset(link,-1,sizeof(link)); for(u=0;u<n;u++) { memset(vis,0,sizeof(vis)); if(dfs(u)) num++; } return num; } int main() { int i,a,t,b; while(scanf("%d",&n)!=EOF) { memset(g,0,sizeof(g)); for(i=0;i<n;i++) { scanf("%d : (%d)",&a,&t); while(t--) { scanf("%d",&b); g[b][a]=1; } } printf("%d\n",n-maxmatch()/2); } }