2022 年牛客多校第十场 E 题题解

E Reviewer Assignment

题意：有 $nn$ 份论文，$mm$ 个人每个人可以审稿这 $nn$ 篇论文中的一些论文。找出一种方案，使得每个人只审核一篇论文的同时，设 $f_{i}f\_i$ 为至少被 $ii$ 个人审核的论文数量，找到 $(f_1,f_2,\cdots ,f_n)(f\_1,f\_2,\backslash cdots,f\_n)$ 的字典序最大值。若有论文没人审核认为不合法。$n,m\le 400n,m\; \backslash leq\; 400$。

解法：考虑费用流。源点 $SS$ 向每个审稿人连接一条费用为 $00$，流量为 $11$ 的边，然后这些人向能审核的论文连接一条流量为 $11$，费用为 $00$ 的边。为了统计被审核次数的最小值，可以让每篇论文向汇点连接 $nn$ 条边，流量均为 $11$，费用依次为 $1,2,\cdots ,n1,2,\backslash cdots,n$。这样在总费用最小的时候，一定是让每篇论文都尽可能的被更多人审核——因为这样分配费用，保证了每个人都有论文看（保证总流量最大）的情况下，让一篇论文审核人数的更多的代价高于去审核一篇没多少人看的论文。或者在分配权值的时候，保证费用单调递增且严格凸即可，以达到上述目的。

#include <bits/stdc++.h>
#define fp(i, a, b) for (int i = a, i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = (b) - 1; i > i##_; --i)

using namespace std;
const int N = 405;
template <const int N, class Ty = int>
class MinCostMaxFlow {
    const Ty Inf = numeric_limits<Ty>::max();
    struct Edge {
        int v;
        Ty cap, cost;
        int rev;
    };
    Ty Sum{}, dis[N]{};
    int n{}, S{}, T{}, aug[N]{};
    bool Augment() {
        fill(dis, dis + n + 1, Inf);
        priority_queue<pair<int, int>> q;
        q.push({dis[T] = 0, T});
        for (int u, v; !q.empty() && q.top().first != Inf;) {
            u = q.top().second, q.pop();
            for (auto E : G[u])
                if (G[v = E.v][E.rev].cap && dis[v] > dis[u] - E.cost)
                    q.push({dis[v] = dis[u] - E.cost, v});
        }
        Sum += dis[S];
        for (int u = 1; u <= n; ++u)
            for (auto &E : G[u])
                E.cost += dis[E.v] - dis[u];
        return dis[S] != Inf;
    }
    Ty dfs(int u, Ty lim) {
        if (u == T)
            return Cost += lim * Sum, lim;
        Ty f = 0;
        int v;
        aug[u] = 1;
        for (auto &E : G[u])
            if (!E.cost && E.cap && !aug[v = E.v]) {
                int t = dfs(v, min(lim - f, E.cap));
                E.cap -= t, G[v][E.rev].cap += t, f += t;
                if (f == lim)
                    break;
            }
        if (f == lim)
            aug[u] = 0;
        return f;
    }

  public:
    vector<Edge> G[N];
    Ty Flow{}, Cost{};
    void Add(int u, int v, Ty a, Ty b) {
        G[u].push_back({v, a, b, (int)G[v].size()});
        G[v].push_back({u, 0, -b, (int)G[u].size() - 1});
    }
    pair<Ty, Ty> work(int _n, int _s, int _t) {
        Ty f;
        n = _n, S = _s, T = _t, Flow = Cost = 0;
        do
            do
                memset(aug, 0, (n + 1) << 2);
            while (Flow += (f = dfs(S, Inf)), f > 0);
        while (Augment());
        return {Flow, Cost};
    }
};
MinCostMaxFlow<N * N, int> D;
using ll = int64_t;
int n, m; char s[N];
void Solve() {
    scanf("%d%d", &n, &m);
    int S = n + m + 1, T = S + 1;
    fp(i, 1, n) {
        D.Add(S, i, 1, 0);
        scanf("%s", s + 1);
        fp(j, 1, m) if (s[j] == '1')
            D.Add(i, n + j, 1, 0);
    }
    fp(i, 1, m)
        fp(j, 1, n)
            D.Add(n + i, T, 1, j);
    auto f = D.work(T, S, T);
    if (f.first != n)
        return puts("-1"), void();
    fp(i, 1, n) {
        for (auto e : D.G[i])
            if (!e.cap && e.v > n) {
                printf("%d ", e.v - n);
                break;
            }
    }
}
int main() {
    int t = 1;
    while (t--) Solve();
    return 0;
}