大型补档计划
题目看的有点晕（语文差）
总体来说就是让每头牛找个谷仓，不能超过容量，最小化每头牛在的谷仓在自己心目中排名的极差。
显然这个最优性问题不好做，但是转换为判定性问题这就是一个标准的二分图多重匹配（即一头牛匹配一个谷仓，一头牛只能匹配一个，一个谷仓接受的牛有上限），所以二分这个极差（显然满足单调性），然后枚举左右端点就行了，跑构建网络跑最大流即可。
时间复杂度 \(O(\sqrt{N}MBLogB)\)，最大边数 \(M = N * B\) 的规模，所以复杂度 \(O(\sqrt{N}N * B ^ 2 LogB)\)，大概 \(5e7\) 的量级，还是能混过去的。
注意每次 \(dfs\) 前清空 \(d\) 数组，太坑了我查了好久。。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1025, S = 25, INF = 1e9;
int n, B, s, t, a[N][S], b[S], d[N], q[N];
int head[N], numE;
struct E{
int next, v, w;
} e[(N * S + N + S) << 1];
void add(int u, int v, int w) {
e[++numE] = (E) { head[u], v, w };
head[u] = numE;
}
void addEdge(int u, int v, int w) {
add(u, v, w), add(v, u, 0);
}
// 建图
void build(int l, int r) {
numE = 1;
memset(head, 0, sizeof head);
for (int i = 1; i <= n; i++) addEdge(s, i, 1);
for (int i = 1; i <= B; i++) addEdge(n + i, t, b[i]);
for (int i = 1; i <= n; i++)
for (int j = l; j <= r; j++) addEdge(i, n + a[i][j], 1);
}
bool bfs() {
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = s, d[s] = 1;
while (hh <= tt) {
int u = q[hh++];
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && !d[v]) {
d[v] = d[u] + 1;
q[++tt] = v;
if (v == t) return true;
}
}
}
return false;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int rest = flow;
for (int i = head[u]; i && rest; i = e[i].next) {
int v = e[i].v;
if (d[v] == d[u] + 1 && e[i].w) {
int k = dinic(v, min(e[i].w, rest));
if (!k) d[v] = 0;
e[i].w -= k, e[i ^ 1].w += k;
rest -= k;
}
}
return flow - rest;
}
// 所有牛排名控制在 x 以内行不行？
bool check(int x) {
for (int l = 1, r; (r = l + x - 1) <= B; l++) {
build(l, r);
int maxflow = 0, res;
while (bfs())
while(res = dinic(s, INF)) maxflow += res;
if(maxflow == n) return true;
}
return false;
}
int main() {
scanf("%d%d", &n, &B);
s = n + B + 1, t = n + B + 2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= B; j++) scanf("%d", &a[i][j]);
for (int i = 1; i <= B; i++) scanf("%d", b + i);
int l = 1, r = B;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", r);
return 0;
}