题目链接：
Poj 3189 Steady Cow Assignment
题目描述：
有n头奶牛，m个棚，每个奶牛对每个棚都有一个喜爱程度。当然啦，棚子也是有脾气的，并不是奶牛想住进来就住进来，超出棚子的最大容量了，棚子是拒绝的。现在要给每个奶牛安家，本宝宝是一个公正无私的人类，所以要找一个奶牛喜爱程度差值最小的方案(虽然这样大家的喜爱程度可能普遍偏低，因为绝对公平并不代表合理啊)，问喜爱程度的区间最小为多大？
解题思路：
每个棚子并不是住一个奶牛，所以是多重匹配咯。匹配的时候二分枚举喜爱程度的区间大小，根据区间大小来枚举区间的起点和终点，然后跑多重匹配判断是否合法即可。注意咯，求得是区间大小，并不是最大喜爱程度与最小喜爱程度的差值。还有啊，还有啊，数据读入的时候maps[i][j]并不是i_th奶牛对j_th棚子的喜爱值，而是i_th奶牛对maps[i][j]棚子的喜爱程度为j。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 1010; 8 int maps[maxn][22], vis[22], used[22][maxn]; 9 int link[22], limit[22], n, m, s, e, mid; 10 bool Find (int u) 11 { 12 for (int i=1; i<=m; i++) 13 {//多重匹配 14 if (!vis[i] && maps[u][i]<e && s<=maps[u][i]) 15 { 16 vis[i] = 1; 17 if (link[i] < limit[i]) 18 {//i棚子未满 19 used[i][link[i] ++] = u; 20 return true; 21 } 22 for (int j=0; j<limit[i]; j++)//i棚子已满，寻找增广路 23 if (Find(used[i][j])) 24 { 25 used[i][j] = u; 26 return true; 27 } 28 } 29 } 30 return false; 31 } 32 bool hungry () 33 { 34 for (s=1; s<=m+1-mid; s++) 35 {//枚举区间起点与终点 36 int ans = 0; 37 e = s + mid; 38 memset (link, 0, sizeof(link)); 39 for (int i=1; i<=n; i++) 40 { 41 memset (vis, 0, sizeof(vis)); 42 if (Find (i)) 43 ans ++; 44 } 45 if (ans == n) 46 return true; 47 } 48 return false; 49 } 50 int main () 51 { 52 while (scanf ("%d %d", &n, &m) != EOF) 53 { 54 for (int i=1; i<=n; i++) 55 for (int j=1; j<=m; j++) 56 { 57 scanf ("%d", &mid); 58 maps[i][mid] = j; 59 } 60 for (int i=1; i<=m; i++) 61 scanf ("%d", &limit[i]); 62 int left = 1, right = m, ans = 0; 63 while (left<=right) 64 {//二分枚举区间 65 mid = (right+left)/2; 66 if (hungry()) 67 { 68 ans = mid; 69 right = mid - 1; 70 } 71 else 72 left = mid + 1; 73 } 74 printf ("%d ", ans); 75 } 76 return 0; 77 }