题目描述：

N头牛（1000），B个农场（20），每个农场可以容纳一定数量的牛。

每头牛对每个农场都有一个排名（排名从1~B）。

每头牛都会在B个农场中的某一个，这头牛的高兴程度是它对这个农场的排名。

为了使每头牛都尽量同等高兴，希望所有牛中最高兴的和最不高兴的程度差值最小，求这个差值。

解题报告：

易知，用最大流是否满流可以判断是否所有牛都被容纳。

然后枚举排名的最高值和最低值（C20,2），每次都连接合法的边，判断是否满流即可。满足条件的差值最小值就是答案。

建图：

超级源点s，和每头牛连接，容量1。超级汇点t，所有农场和t连接，容量是农场的容量。

如果牛i对农场j的排名在当前枚举的范围内，连接i，j容量1。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n, b, g[1000][20], cap[20], ans;
#define Max 0x1fffffff
#define size 1200
struct edge{int from, to, val, next;}e[100000];
int v[size], que[size], dis[size], cnt, cur[size];
void insert(int from, int to, int va)
{
    e[cnt].from = from, e[cnt].to = to; e[cnt].val = va;
    e[cnt].next = v[from];v[from] = cnt ;
    e[cnt].from = to, e[cnt].to = from; e[cnt].val = 0;
    e[cnt].next = v[to];v[to] = cnt ;
}
bool bfs(int n, int s, int t)
{
    int head, tail, id;
    head = tail = 0; que[tail ] = s;
    memset(dis, -1, sizeof(int) * n);dis[s] = 0;
    while(head < tail) // bfs,得到顶点i的距s的最短距离dis[i]
        for(id = v[que[head ]]; id != -1; id = e[id].next)
            if (e[id].val > 0 && dis[e[id].to] == -1)
            {
                dis[e[id].to] = dis[e[id].from] 1;
                que[tail ] = e[id].to;
                if (e[id].to == t) return true;
            }
    return false;
}

int Dinic(int n, int s, int t)
{
    int maxflow = 0, tmp, i;
    while(bfs(n, s, t))
    {
        int u = s, tail = 0;
        for(i = 0; i < n; i ) cur[i] = v[i];
        while(cur[s] != -1)
            if (u != t && cur[u] != -1 && e[cur[u]].val > 0 && dis[u] != -1 && dis[u] 1 == dis[e[cur[u]].to])
            {que[tail ] = cur[u]; u = e[cur[u]].to;}
            else if (u == t)
            {
                for(tmp = Max, i = tail - 1; i >= 0; i--) tmp = min(tmp, e[que[i]].val);
                for(maxflow = tmp, i = tail - 1; i >= 0; i--)
                {
                    e[que[i]].val -= tmp;
                    e[que[i] ^ 1].val = tmp;
                    if (e[que[i]].val == 0) tail = i;
                }
                u = e[que[tail]].from;
            }
            else
            {
                while(tail > 0 && u != s && cur[u] == -1) u = e[que[--tail]].from;
                cur[u] = e[cur[u]].next;
            }
    }
    return maxflow;
}
int main()
{
    while(scanf("%d%d", &n, &b) != EOF)
    {
        for(int i = 0; i < n; i )
            for(int j = 0; j < b; j )
                scanf("%d", &g[i][j]), g[i][j]--;
        for(int i = 0; i < b; i )
            scanf("%d", &cap[i]);
        for(int len = 1; len <= b; len )
        {
            for(int i = 0; i len - 1 < b; i )
            {
                memset(v, -1, sizeof(int) * (n b 3));
                int s = n b; int t = s 1; cnt = 0;
                for(int j = 0; j < n; j ) insert(s, j, 1);
                for(int j = n; j < n b; j ) insert(j, t, cap[j - n]);
                for(int j = 0; j < n; j )
                    for(int k = i; k <= i len - 1; k ) insert(j, g[j][k] n, 1);
                if (Dinic(t 1, s, t) == n)
                {
                    ans = len;
                    goto lable;
                }
            }
        }
        lable:
        printf("%d\n", ans);
    }
    return 0;
}