題意：

一些奶牛只有在特定的圍欄中才能產奶，要求合理安排使能產奶的奶牛數達到最大。

要點：

二分圖裸題，最近剛學了二分圖，看下面的參考博客，寫的比較好：

參考博客：匈牙利算法

15479500

Seasonal

1274

Accepted

520K

16MS

C++

736B

2016-05-07 20:26:59

#include<stdio.h> #include<stdlib.h> #include<string.h> int map[300][300], used[300],girl[300]; int n, m;bool find(int x) {int i;for (i = 1; i <= m; i++){if (map[x][i] && !used[i]){used[i] = 1;if (girl[i] == -1 || find(girl[i]))//女孩還沒人追或者追的人可以挪動{girl[i] = x;return true;}}}return false; }int main() {int i, num,temp;while (scanf("%d%d", &n, &m) != EOF){memset(map, 0, sizeof(map));memset(girl, -1, sizeof(girl));for (i = 1; i <= n; i++){scanf("%d", &num);while (num--){scanf("%d", &temp);map[i][temp] = 1;}}int num = 0;for (i = 1; i <= n; i++){memset(used, 0, sizeof(used));//每次都要重新賦值為0if (find(i))num++;}printf("%d\n", num);}return 0; }

轉載于:https://www.cnblogs.com/seasonal/p/10343749.html

總結

以上是生活随笔為你收集整理的POJ1274 The Perfect Stall(二分图)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。