CF628F Bear and Fair Set

· · 题解

Analysis

首先这道题有特别多的约束条件：

这些条件，尤其是最后一条，可以联想到网络流。

Details

建出超级源点与超级汇点。

首先是把那个“集合的提示”转化成“有恰好 k 个值在 [l,r] 中”。并把超级源点与每个区间相连，边的最大流量就是 k_i。

再把每段区间与其中能取到的所有可能值建边。由于每个值只能取到一次（集合的互异性），所以边的最大流量为 1。

然后把所有能取到的值按对 5 的模数分类。这个边的流量无所谓，只要大于 1 就行，因为前面已经有限制了，无论如何流过来的最大都是 1。

最后把这 5 个点与超级汇点相连，此时边的最大流量为 \frac{n}{5}。

连出来就是下面这个东西。

我们需要恰好后面的 5 条边流量都要是 \frac{n}{5}，所以每条都要跑满，总流量就要是且恰好是 n。跑最大流判断是不是就行了。

Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
#include <utility>

using ll = long long int;
using pii = std::pair <int, int>;
constexpr int MAXN = 1e4 + 10;

struct Dinic {
    struct edge {
        int v; ll cap; int rev;
        edge(int _v, ll _cap, int _rev) : v(_v), cap(_cap), rev(_rev) {}
    };

    int superS, superT;
    std::vector <std::vector <edge> > G;
    std::vector <int> dep, lst;

    Dinic(int l, int s, int t) : superS(s), superT(t), G(l + 1), dep(l + 1), lst(l + 1) {}

    inline void addEdge(int u, int v, ll w) {
        G[u].push_back(edge(v, w, G[v].size()));
        G[v].push_back(edge(u, 0, G[u].size() - 1));
    }

    inline bool bfs() {
        std::fill(dep.begin(), dep.end(), 0);

        std::queue <int> q;
        q.push(superS);
        dep[superS] = 1;

        while (!q.empty()) {
            int u = q.front(); q.pop();

            for (auto [v, cap, rev] : G[u]) {
                if (dep[v] || cap <= 0) continue;
                q.push(v);
                dep[v] = dep[u] + 1;

                if (v == superT)
                    return true;
            }
        }

        return false;
    }

    ll dfs(int u, ll lim) {
        if (lim <= 0 || u == superT)
            return lim;

        ll ret = lim, tot = 0;
        for (int& k = lst[u]; k < (int)G[u].size(); k++) {
            auto& [v, cap, rev] = G[u][k];

            if (cap > 0 && dep[v] == dep[u] + 1) {
                ll t = dfs(v, std::min(ret, cap));
                ret -= t, tot += t;
                cap -= t, G[v][rev].cap += t;
            }

            if (ret <= 0)
                break;
        }

        return tot;
    }

    ll maxFlow() {
        ll res = 0;
        while (bfs()) {
            std::fill(lst.begin(), lst.end(), 0);
            res += dfs(superS, LLONG_MAX);
        }
        return res;
    }
};

int n, m, q;

pii limit[MAXN];
int l[MAXN], r[MAXN], k[MAXN];

int main() {
    std::cin >> n >> m >> q;

    for (int i = 1; i <= q; i++)
        std::cin >> limit[i].first >> limit[i].second;
    limit[++q] = {m, n};

    std::sort(limit + 1, limit + 1 + q);

    for (int i = 1; i <= q; i++) {
        int len = limit[i].first - limit[i-1].first;
        int need = limit[i].second - limit[i-1].second;
        if (need < 0 || need > len) {
            std::cout << "unfair";
            return 0;
        }
    }

    int s = m + q + 6, t = m + q + 7;
    Dinic net(m + q + 7, s, t);

    for (int i = 1; i <= q; i++)
        net.addEdge(s, i, limit[i].second - limit[i - 1].second);

    for (int i = 1; i <= q; i++) {
        for (int j = limit[i - 1].first + 1; j <= limit[i].first; j++)
            net.addEdge(i, j + q, 1);
    }

    for (int i = 1; i <= m; i++)
        net.addEdge(i + q, q + m + (i % 5) + 1, 1);

    for (int i = 1; i <= 5; i++)
        net.addEdge(q + m + i, t, n / 5);

    if (net.maxFlow() == n) std::cout << "fair";
    else std::cout << "unfair";

    return 0;
}