【题意】：给出n头牛，b个农场，每个农场可以容纳一定数目的牛，每头牛对这B个农场都有一个确定的排名。为了使每头牛都尽量同等高兴，希望所有牛中最高兴的和最不高兴的程度差值最小，求这个差值。
【题解】：构图：源点s向每头牛连边，容量为1，表示每头牛只能选择一个农场；每个农场向汇点t连边，容量为农场可容纳牛的数目；二分枚举程度差值，如果牛i 对农场j 的排名在枚举的范围内，那么连边i->j，容量为1.对于每次二分枚举，判断构图后的最大流是否等于牛的数目即可。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 #define maxn 1100
6 #define maxm 150000
7 const int inf = 1 << 30;
8 int n, m, s, t, b;
9 int eh[maxn], low[maxn], pre[maxn], cur[maxn], tot, cnt[maxn], dist[maxn];
10 int cow[1005][25], cap[25];
11 struct Edge {
12 int u, v, cap, flow, next;
13 }et[maxm];
14
15 void init() {
16 tot = 0;
17 memset(eh, -1, sizeof(eh));
18 }
19
20 void add(int u, int v, int cap, int flow) {
21 Edge e = {u, v, cap, flow, eh[u]};
22 et[tot] = e;
23 eh[u] = tot++;
24 }
25
26 void addedge(int u, int v, int cap) {
27 add(u, v, cap, 0), add(v, u, 0, 0);
28 }
29
30 int isap(int s, int t, int n) {
31 int u, v, now, flow = 0;
32 memset(dist, 0, sizeof(dist));
33 memset(cnt, 0, sizeof(cnt));
34 memset(low, 0, sizeof(low));
35 for(u = 0; u <= n; u++) cur[u] = eh[u];
36 low[s] = inf, cnt[0] = n;
37 u = s;
38 while(dist[s] < n) {
39 for(now = cur[u]; now != -1; now = et[now].next)
40 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1)
41 break;
42 if(now != -1) {
43 cur[u] = pre[v] = now;
44 low[v] = min(low[u], et[now].cap - et[now].flow);
45 u = v;
46 if(u == t) {
47 for(; u != s; u = et[pre[u]].u) {
48 et[pre[u]].flow += low[t];
49 et[pre[u]^1].flow -= low[t];
50 }
51 low[s] = inf, flow += low[t];
52 }
53 } else {
54 if(--cnt[dist[u]] == 0) break;
55 dist[u] = n, cur[u] = eh[u];
56 for(now = eh[u]; now != -1; now = et[now].next)
57 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
58 dist[u] = dist[et[now].v] + 1;
59 cnt[dist[u]]++;
60 if(u != s) u = et[pre[u]].u;
61 }
62 }
63 return flow;
64 }
65
66 bool build(int rank) {
67 for(int st = 1; st <= b - rank + 1; st++) {
68 init();
69 s = 0; t = n + b + 1;
70 for(int i = 1; i <= n; i++) {
71 addedge(s, i, 1);
72 for(int j = st; j <= st + rank - 1; j++)
73 addedge(i, n + cow[i][j], 1);
74 }
75 for(int i = 1; i <= b; i++) addedge(n + i, t, cap[i]);
76 if(isap(s, t, t - s + 1) == n) return true;
77 }
78 return false;
79 }
80
81 int solve() {
82 int l = 1, r = b, res = -1;
83 while(l <= r) {
84 int mid = (l + r) >> 1;
85 if(build(mid)) res = mid, r = mid - 1;
86 else l = mid + 1;
87 }
88 return res;
89 }
90
91 int main() {
92 scanf("%d%d", &n, &b);
93 for(int i = 1; i <= n; i++)
94 for(int j = 1; j <= b; j++)
95 scanf("%d", &cow[i][j]);
96 for(int i = 1; i <= b; i++) scanf("%d", &cap[i]);
97 int ans = solve();
98 printf("%d\n", ans);
99 return 0;
100 }
101