思路：

這題完全不懂，看了這份大牛的解題報(bào)告
http://hi.baidu.com/winterlegend/blog/item/2411981e8fd0ed6bf724e45e.html
發(fā)現(xiàn)嗎的太牛逼了！

首先二分圖匹配，正常情況下，都是單個(gè)單個(gè)的點(diǎn)這樣匹配、
但是像這道題，右邊的點(diǎn)一個(gè)可以匹配好幾個(gè)左邊的點(diǎn)。也是用匈牙利算法，不過(guò)要做少少修改。

枚舉答案的時(shí)候，有兩種方法：
一個(gè)是移動(dòng)區(qū)間的方法。復(fù)雜度O(B)。注意，只移動(dòng)區(qū)間右邊的時(shí)候不用重新匹配，只需要接著上次沒(méi)匹配完的繼續(xù)匹配就行了
一個(gè)是二分法。復(fù)雜度 O(B lgB)
由于數(shù)據(jù)的問(wèn)題，這兩種方法時(shí)間相差無(wú)幾。在 16ms 和 32ms 之間。

#include <stdio.h>

struct barn {
    int link[1024], cnt, vis, cap;
};
struct cow {
    int rank[32];
};

struct barn barns[32];
struct cow cows[1024];
int start, end, last_pos;
int N, B, tm;

int dfs(int c)
{
    int i, j;
    struct barn *b;

    for (i = start; i <= end; i++) {
        b = &barns[cows[c].rank[i]];
        if (b->vis == tm)
            continue;
        b->vis = tm;
        if (b->cnt < b->cap) {
            b->link[b->cnt++] = c;
            return 1;
        }
        for (j = 0; j < b->cap; j++)
            if (dfs(b->link[j])) {
                b->link[j] = c;
                return 1;
            }
    }
    return 0;
}

inline void init()
{
    int i;

    for (i = 1; i <= B; i++)
        barns[i].cnt = 0;
    last_pos = 1;
}

inline int match()
{
    int i, j;

    for (i = last_pos; i <= N; i++) {
        tm++;
        if (!dfs(i))
            break;
    }
    last_pos = i;
    return i > N;
}

int main()
{
    int i, j, ans;

    freopen("e:\\test\\in.txt", "r", stdin);

    scanf("%d%d", &N, &B);
    for (i = 1; i <= N; i++)
        for (j = 1; j <= B; j++)
            scanf("%d", &cows[i].rank[j]);
    for (i = 1; i <= B; i++)
        scanf("%d", &barns[i].cap);
    
#if 0
    // O(B)
    ans = B;
    start = end = 1;
    while (start <= B && end <= B) {
        init();
        while (end <= B && !match())
            end++;
        if (end - start + 1 < ans)
            ans = end - start + 1;
        start++;
    }
#else
    // O(B*lgB)
    int l, r, m;

    l = 1;
    r = B;
    while (l <= r) {
        m = (l + r) / 2;
        for (start = 1; start <= B - m + 1; start++) {
            end = start + m - 1;
            init();
            if (match())
                break;
        }
        if (start == B - m + 2) {
            // failed
            l = m + 1;
        } else 
            r = m - 1;
    }
    ans = r + 1;
#endif

    printf("%d\n", ans);

    return 0;
}