题解 P2857 【[USACO06FEB]稳定奶牛分配Steady Cow Assignment】

· · 题解

Description

给定 n 头牛和 b 座牛棚，已知每头牛最喜欢，第 2 喜欢，第 3 喜欢，……，第 b 喜欢的牛棚分别是什么，以及每个牛棚的容量 v_i（最多能住 v_i 头牛）。如果某头牛住在第 i 喜欢的牛棚里，则这头牛的不满意度为 i 。求如何分配牛棚，使所有牛的 最大不满意度 - 最小不满意度 + 1 的值最小。输出这个值是多少。

(1 \leq n \leq 10^3,1 \leq b \leq 20,\sum\limits_{i = 1}^n v_i = n)

Solution

考虑 网络流 + 二分答案 。

我们可以把图分成两部分。左部点是牛，右部点是牛棚。

在源点与每头牛之间连一条流量为 1 的边（一头牛最大贡献为 1），在第 i 个牛棚与汇点之间连一条流量为 v_i 的边（一个牛棚最大贡献为 v_i）。

对于样例所建出的图：

牛和牛棚之间的边呢？显然不能直接全部连上。

我们可以 二分答案（假设答案为 x），然后枚举所有牛的 最小不满意度 i，那么 最大不满意度 为 i + x - 1 。

即每头牛不满意度所在的区间为 [i,i + x - 1] 。也就是说，对于每一头牛，我们只需要在它与它第 i \sim i + x - 1 喜欢的牛棚之间连一条流量为 1 的边。接着用 \rm dinic 跑一遍最大流，若最大流为 n，则这个答案可行。

不过由于数据范围比较小，暴力枚举也能过。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 2e3, MAXB = 20, MAXM = 1e5, INF = 0x3f3f3f3f;
int n, b, ans, tot, head[MAXN + 5], cur[MAXN + 5], depth[MAXN + 5];
int v[MAXB + 5], f[MAXN + 5][MAXB + 5];
struct Edge {
    int next, to, dis;
} e[MAXM + 5];

inline void addEdge(int u, int v, int w) {
    e[++tot] = (Edge) { head[u], v, w };
    head[u] = tot;
}

inline bool bfs(int s, int t) {
    for (int i = 0; i <= t; ++i) cur[i] = head[i];
    memset(depth, 0, sizeof (depth));
    queue<int> q;
    depth[s] = 1;
    q.push(s);
    for (; !q.empty(); ) {
        int u = q.front();
        q.pop();
        for (int v, w, i = head[u]; v = e[i].to, w = e[i].dis, i; i = e[i].next) {
            if (depth[v] || !w) continue;
            depth[v] = depth[u] + 1;
            if (v == t) return 1;
            q.push(v);
        }
    }
    return 0;
}

int dinic(int u, int t, int flow) {
    if (u == t) return flow;
    int rest = flow;
    for (int v, w, i = cur[u]; v = e[i].to, w = e[i].dis, i && rest; i = e[i].next) {
        cur[u] = i;//当前弧优化 
        if (depth[v] != depth[u] + 1 || !w) continue;
        int k = dinic(v, t, min(rest, w));
        if (!k) depth[v] = 0;
        else {
            e[i].dis -= k;
            e[i ^ 1].dis += k;
            rest -= k;
        }
    }
    return flow - rest;
}

inline int maxFlow(int s, int t) {
    int res = 0;
    for (; bfs(s, t); ) res += dinic(s, t, INF);
    return res;
}

inline bool check(int x) {//检查答案 x
    for (int i = 1; i + x - 1 <= b; ++i) {
        //最小满意度为 i，最大满意度为 i + x - 1
        tot = 1;
        memset(head, 0, sizeof (head));
        int s = 0, t = n + b + 1;//源点编号和汇点编号 
        for (int j = 1; j <= n; ++j)//源点与牛连一条流量为 1 的边 
            addEdge(s, j, 1), addEdge(j, s, 0);
        for (int j = 1; j <= b; ++j)//牛棚与汇点连一条流量为 v[j] 的边 
            addEdge(j + n, t, v[j]), addEdge(t, j + n, 0);
        //与第 i ~ i + x - 1 喜欢的牛棚连一条流量为 1 的边
        for (int j = 1; j <= n; ++j)
            for (int k = i; k <= i + x - 1; ++k)
                addEdge(j, f[j][k] + n, 1), addEdge(f[j][k] + n, j, 0);
        if (maxFlow(s, t) == n) return 1;//若最大流为 n，则该答案可行 
    }
    return 0;
}

int main() {
    read(n), read(b);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= b; ++j)
            read(f[i][j]);//第 i 头牛第 j 喜欢的牛棚是 f[i][j] 
    for (int i = 1; i <= b; ++i) read(v[i]);
    for (int mid, l = 1, r = b; l <= r; ) {//二分答案 
        mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        } else l = mid + 1;
    }
    write(ans);
    putchar('\n');
    return 0;
}