题目链接：http://poj.org/problem?id=3189
题意：有n头牛，B个牛棚，每头牛对牛棚都有一个喜欢度，接下来输入N*B的矩阵第i行第j列的数x表示:第i头牛第j喜欢的是x;
第i个牛棚最多存Max[i]头牛，最后求牛棚的排名区间，意思就是假如一个牛棚中有最喜欢这个牛棚的牛（那么就是第一喜欢1）和也有最不喜欢这个牛棚的牛（那么就是第B喜欢B），答案就是1--B的区间大小B-1+1，问怎么安排能让这个区间值最小，求最小值；
由于B的取值范围较小，所以可以枚举所有的区间，求符合条件的最小值，由于牛棚里可能不止放一头牛，所以是多重匹配；
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
#include <string>
#include <set>
using namespace std;
#define N 1005
#define INF 0x3f3f3f3f
#define met(a, b) memset(a, b, sizeof(a))
typedef long long LL; struct node
{
int k, a[N];
}used[N]; int B, n, vis[N];
int G[N][N], Max[N]; bool Find(int u, int L, int R)
{
for(int i=; i<=B; i++)
{
if( !vis[i] && G[u][i]>=L && G[u][i]<=R)///所有的大小应在此范围内；
{
vis[i] = ;
if( used[i].k < Max[i] )
{
used[i].a[ used[i].k++ ] = u;
return true;
}
for(int j=; j<used[i].k; j++)
{
if( Find(used[i].a[j], L, R) )
{
used[i].a[j] = u;
return true;
}
}
}
}
return false;
} bool Hungary(int L, int R)
{
met(used, );
for(int i=; i<=n; i++)
{
met(vis, );
if( !Find(i, L, R) )
return false;
}
return true;
} int main()
{
while(scanf("%d %d", &n, &B) != EOF)
{
met(G, ); for(int i=; i<=n; i++)
{
for(int j=; j<=B; j++)
{
int x;
scanf("%d", &x);
G[i][x] = j;
}
}
for(int i=; i<=B; i++)
scanf("%d", &Max[i]); int L = , R = B, ans = R;
while(L <= R)
{
int i, Mid = (L+R)/; for(i=; i<=B; i++)
{
if( Hungary(i, Mid+i) )///枚举区间大小为Mid+1的值，满足条件时则取其最小值；
break;
}
if(i == B+)
L = Mid+;
else
R = Mid-, ans = Mid+;
}
printf("%d\n", ans);
}
return ;
}