有n头奶牛，m个牛圈，奶牛只有在自己喜欢的牛圈里才会产奶，问最多有多少奶牛能产奶。
明显是求最大匹配
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 using namespace std; 7 const int maxn=205; 8 int n,m; 9 vector<int> map[maxn]; 10 int link[maxn],vis[maxn]; 11 bool dfs(int t) 12 { 13 int i,x,size=map[t].size(); 14 for(i=0;i<size;i++) 15 { 16 x=map[t][i]; 17 if(!vis[x]) 18 { 19 vis[x]=1; 20 if(link[x]==-1||dfs(link[x])) 21 { 22 link[x]=t; 23 return 1; 24 } 25 } 26 } 27 return 0; 28 } 29 int main() 30 { 31 int i,j,a,b,ans; 32 while(~scanf("%d%d",&n,&m)) 33 { 34 for(i=1;i<=n;i++) 35 { 36 map[i].clear(); 37 scanf("%d",&a); 38 for(j=1;j<=a;j++) 39 { 40 scanf("%d",&b); 41 map[i].push_back(b); 42 } 43 } 44 ans=0; 45 memset(link,-1,sizeof(link)); 46 for(i=1;i<=n;i++) 47 { 48 memset(vis,0,sizeof(vis)); 49 if(dfs(i)) ans++; 50 } 51 printf("%d ",ans); 52 } 53 }