嗯...

 

题目链接：http://poj.org/problem?id=1274

 

一道很经典的匈牙利算法的题目：

将每只奶牛看成二分图中左边的点，将牛圈看成二分图中右边的点，如果奶牛看上某个牛圈，就将两点之间连边，然后跑一边匈牙利就行了...

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 int n, m, match[205], g[205][205], vis[205];  8  9 inline int dfs(int u){10     for(int i = 1; i <= m; i++){11         if(g[u][i] && !vis[i]){12             vis[i] = 1;13             if(!match[i] || dfs(match[i])){14                 match[i] = u;15                 return 1;16             }17         }18     }19     return 0;20 }21 22 inline int hungary(){23     int ans = 0;24     for(int i = 1; i <= n; i++){25         memset(vis, 0, sizeof(vis));26         if(dfs(i)) ans++;27     }28     return ans;29 }30 31 int main(){32     while(~scanf("%d%d", &n, &m)){33         memset(g, 0, sizeof(g));34         memset(match, 0, sizeof(match));35         for(int i = 1; i <= n; i++){36             int s;37             scanf("%d", &s);38             for(int j = 1; j <= s; j++){39                 int t;40                 scanf("%d", &t);41                 g[i][t] = 1;42             }43         }44         printf("%d\n", hungary());45     }46     return 0;47 }