題意：每個奶牛對所有的牛棚有個排名（根據喜歡程度排的），每個牛棚能夠入住的牛的數量有個上限，重新給牛分配牛棚，使牛棚在牛心中的排名差（所有牛中最大排名和最小排名之差）最小。
牛棚個數最多為20，那麼直接枚舉最差排名和最好排名，對於每種情況判斷是否合法，取最小值。
構圖：
源點與每頭牛之間連接一條邊，邊權為1，每頭牛與枚舉范圍內的牛棚之間連接一條邊，邊權為1（表示每頭牛可以入住的牛棚），然後每個牛棚與匯點之間建立一條邊，邊權為每個牛棚的入住上限。
換了一個模板，那個Dinic模板用鄰接矩陣存儲的，速度太慢了。這個模板非常優秀，只是有點長了。
[cpp]
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
#define N 1200
#define M 50220
#define INF 0x3f3f3f3f
class MaxFlow {
public:
struct record {
int v, f, next;
} edge[M];
int n, s, t;
int pos[N], dis[N], vh[N], cl;
int his[N], di[N], pre[N];
void AddEdge(int a, int b, int f) {
cl++;
edge[cl].next = pos[a];
edge[cl].v = b;
edge[cl].f = f;
pos[a] = cl;
cl++;
edge[cl].next = pos[b];
edge[cl].v = a;
edge[cl].f = 0; //若為無向邊，則f = f
pos[b] = cl;
}
void Init() {
cl = 1;
memset(dis, 0, sizeof(dis));
memset(vh, 0, sizeof(vh));
memset(pos, 0, sizeof(pos));
}
int flow() {
vh[0] = n; //初始化GAP數組（默認所有點的距離標號均為0，則距離標號為0的點數量為n）
for (int i = 0; i < n; i++) di[i] = pos[i]; //初始化當前弧
int i = s, aug = INF, flow = 0; //初始化一些變量，flow為全局流量，aug為當前增廣路的流量
bool flag = false; //標記變量，記錄是否找到了一條增廣路（若沒有找到則修正距離標號）
while (dis[s] < n) {
his[i] = aug; //保存當前流量
flag = false;
for (int p=di[i]; p; p=edge[p].next)
if ((edge[p].f > 0) && (dis[edge[p].v] + 1 == dis[i])) {//利用距離標號判定可行弧
flag = true; //發現可行弧
di[i] = p; //更新當前弧
aug = min(aug, edge[p].f); //更新當前流量
pre[edge[p].v] = p; //記錄前驅結點
i = edge[p].v; //在弧上向前滑動
if (i == t) {//遇到匯點，發現可增廣路
flow += aug; //更新全局流量
while (i != s) {//減少增廣路上相應弧的容量，並增加其反向邊容量
edge[pre[i]].f -= aug;
edge[pre[i]^1].f += aug;
i = edge[pre[i]^1].v;
}
aug = INF;
}
break;
}
if (flag) continue; //若發現可行弧則繼續，否則更新標號
int min = n - 1;
for (int p=pos[i]; p; p=edge[p].next)
if ((edge[p].f > 0) && (dis[edge[p].v] < min)) {
di[i] = p; //不要忘了重置當前弧
min = dis[edge[p].v];
}
--vh[dis[i]];
if (vh[dis[i]] == 0) break; //更新vh數組，若發現距離斷層，則算法結束（GAP優化）
dis[i] = min + 1;
++vh[dis[i]];
if (i != s) {//退棧過程
i = edge[pre[i]^1].v;
aug = his[i];
}
}
return flow;
}
} net;
int n, b, g[1002][22], s[22];
void init(int x, int y) {
net.Init();
net.s = 0, net.t = n+b+1, net.n = n+b+2;
for (int i=1; i<=n; i++) net.AddEdge(0, i, 1);
for (int i=1; i<=n; i++) for (int j=x; j<=y; j++)
net.AddEdge(i, g[i][j]+n, 1);
for (int i=1; i<=b; i++) net.AddEdge(n+i, net.t, s[i]);
}
int main() {
scanf("%d%d", &n, &b);
for (int i=1; i<=n; i++) for (int j=1; j<=b; j++) scanf(" %d", &g[i][j]);
for (int i=1; i<=b; i++) scanf("%d", &s[i]);
int ans = INF;
for (int i=1; i<=b; i++) for (int j=i; j<=b; j++) {
init(i, j);
if (net.flow() == n) ans = min(ans, j-i+1);
}
printf("%d\n", ans);
return 0;
}
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
#define N 1200
#define M 50220
#define INF 0x3f3f3f3f
class MaxFlow {
public:
struct record {
int v, f, next;
} edge[M];
int n, s, t;
int pos[N], dis[N], vh[N], cl;
int his[N], di[N], pre[N];
void AddEdge(int a, int b, int f) {
cl++;
edge[cl].next = pos[a];
edge[cl].v = b;
edge[cl].f = f;
pos[a] = cl;
cl++;
edge[cl].next = pos[b];
edge[cl].v = a;
edge[cl].f = 0; //若為無向邊，則f = f
pos[b] = cl;
}
void Init() {
cl = 1;
memset(dis, 0, sizeof(dis));
memset(vh, 0, sizeof(vh));
memset(pos, 0, sizeof(pos));
}
int flow() {
vh[0] = n; //初始化GAP數組（默認所有點的距離標號均為0，則距離標號為0的點數量為n）
for (int i = 0; i < n; i++) di[i] = pos[i]; //初始化當前弧
int i = s, aug = INF, flow = 0; //初始化一些變量，flow為全局流量，aug為當前增廣路的流量
bool flag = false; //標記變量，記錄是否找到了一條增廣路（若沒有找到則修正距離標號）
while (dis[s] < n) {
his[i] = aug; //保存當前流量
flag = false;
for (int p=di[i]; p; p=edge[p].next)
if ((edge[p].f > 0) && (dis[edge[p].v] + 1 == dis[i])) {//利用距離標號判定可行弧
flag = true; //發現可行弧
di[i] = p; //更新當前弧
aug = min(aug, edge[p].f); //更新當前流量
pre[edge[p].v] = p; //記錄前驅結點
i = edge[p].v; //在弧上向前滑動
if (i == t) {//遇到匯點，發現可增廣路
flow += aug; //更新全局流量
while (i != s) {//減少增廣路上相應弧的容量，並增加其反向邊容量
edge[pre[i]].f -= aug;
edge[pre[i]^1].f += aug;
i = edge[pre[i]^1].v;
}
aug = INF;
}
break;
}
if (flag) continue; //若發現可行弧則繼續，否則更新標號
int min = n - 1;
for (int p=pos[i]; p; p=edge[p].next)
if ((edge[p].f > 0) && (dis[edge[p].v] < min)) {
di[i] = p; //不要忘了重置當前弧
min = dis[edge[p].v];
}
--vh[dis[i]];
if (vh[dis[i]] == 0) break; //更新vh數組，若發現距離斷層，則算法結束（GAP優化）
dis[i] = min + 1;
++vh[dis[i]];
if (i != s) {//退棧過程
i = edge[pre[i]^1].v;
aug = his[i];
}
}
return flow;
}
} net;
int n, b, g[1002][22], s[22];
void init(int x, int y) {
net.Init();
net.s = 0, net.t = n+b+1, net.n = n+b+2;
for (int i=1; i<=n; i++) net.AddEdge(0, i, 1);
for (int i=1; i<=n; i++) for (int j=x; j<=y; j++)
net.AddEdge(i, g[i][j]+n, 1);
for (int i=1; i<=b; i++) net.AddEdge(n+i, net.t, s[i]);
}
int main() {
scanf("%d%d", &n, &b);
for (int i=1; i<=n; i++) for (int j=1; j<=b; j++) scanf(" %d", &g[i][j]);
for (int i=1; i<=b; i++) scanf("%d", &s[i]);
int ans = INF;
for (int i=1; i<=b; i++) for (int j=i; j<=b; j++) {
init(i, j);
if (net.flow() == n) ans = min(ans, j-i+1);
}
printf("%d\n", ans);
return 0;
}
