思路：
這題完全不懂，看了這份大牛的解題報告
http://hi.baidu.com/winterlegend/blog/item/2411981e8fd0ed6bf724e45e.html
發(fā)現(xiàn)嗎的太牛逼了！
首先二分圖匹配，正常情況下，都是單個單個的點這樣匹配、
但是像這道題，右邊的點一個可以匹配好幾個左邊的點。也是用匈牙利算法，不過要做少少修改。
枚舉答案的時候，有兩種方法：
一個是移動區(qū)間的方法。復雜度O(B)。注意，只移動區(qū)間右邊的時候不用重新匹配，只需要接著上次沒匹配完的繼續(xù)匹配就行了
一個是二分法。復雜度 O(B lgB)
由于數(shù)據(jù)的問題，這兩種方法時間相差無幾。在 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;
}