Solution Set 2023.12.4

标签：std typedef Set const 2023.12 valueType flow Solution false

来衡实了，感觉良好。

[NOIP2023] 三值逻辑

一直以为是写假了，结果是写挂了，没有判自环的同时 \(u, v\) 输入反了。

考虑对于每个变量的每个版本均开一个节点，那么赋值关系可以用有向边表示，可以发现最终得到的一定是若干外向基环树和若干外向树组成的图。且被 \(\tt{T,F,U}\) 三种指令赋值的节点一定是外向树的根，不会引起冲突。因此只需要考虑所有的基环树即可。从基环树的环开始递归染色，若冲突则整课树的值均为 \(\tt{U}\)。

Code

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<bool> bitset;
typedef std::queue<valueType> ValueQueue;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;

valueType N, M, S;
ValueVector color, now, degree;
PairMatrix G;
ValueMatrix revG;
bitset undefined;

bool push(valueType x) {
    bool success = true;

    undefined[x] = false;

    for (auto const &[to, w] : G[x]) {
        if (undefined[to]) {
            color[to] = color[x] * w;
            undefined[to] = false;

            if (!push(to))
                success = false;
        } else {
            if (color[to] != color[x] * w)
                success = false;
        }
    }

    return success;
}

void pushZero(valueType x) {
    color[x] = 0;

    for (auto const &[to, w] : G[x]) {
        if (color[to] != 0)
            pushZero(to);
    }
}

void solve() {
    std::cin >> N >> M;

    S = N + M;

    color.resize(S + 1, 1);
    G.resize(S + 1);
    revG.resize(S + 1);
    undefined.resize(S + 1, true);
    degree.resize(S + 1, 0);
    now.resize(N + 1);
    std::iota(now.begin(), now.end(), 0);

    valueType count = N;

    for (valueType m = 0; m < M; ++m) {
        char type;

        std::cin >> type;

        if (type == 'T') {
            valueType x;

            std::cin >> x;

            now[x] = ++count;

            undefined[now[x]] = false;

            color[now[x]] = 1;
        } else if (type == 'F') {
            valueType x;

            std::cin >> x;

            now[x] = ++count;

            undefined[now[x]] = false;

            color[now[x]] = -1;
        } else if (type == 'U') {
            valueType x;

            std::cin >> x;

            now[x] = ++count;

            undefined[now[x]] = false;

            color[now[x]] = 0;
        } else if (type == '+') {
            valueType u, v;

            std::cin >> v >> u;

            valueType const from = now[u];

            now[v] = ++count;

            G[from].emplace_back(now[v], 1);
            assert(undefined[now[v]]);
            revG[now[v]].emplace_back(from);
            ++degree[from];
        } else {
            valueType u, v;

            std::cin >> v >> u;

            valueType const from = now[u];

            now[v] = ++count;

            G[from].emplace_back(now[v], -1);
            assert(undefined[now[v]]);
            revG[now[v]].emplace_back(from);
            ++degree[from];
        }
    }

    for (valueType i = 1; i <= N; ++i) {
        G[now[i]].emplace_back(i, 1);
        assert(undefined[i]);
        revG[i].emplace_back(now[i]);
        ++degree[now[i]];
    }

    assert(count == S);

    S = count;

    bitset const undefinedCopy = undefined;

    for (valueType i = 1; i <= S; ++i) {
        if (undefinedCopy[i])
            continue;

        assert(revG[i].empty());

        undefined[i] = false;

        if (!push(i))
            std::abort();
    }

    ValueQueue Q;

    for (valueType i = 1; i <= S; ++i) {
        if (degree[i] == 0)
            Q.push(i);
    }

    while (!Q.empty()) {
        valueType const x = Q.front();

        Q.pop();

        for (auto const &iter : revG[x])
            if (--degree[iter] == 0)
                Q.push(iter);
    }

    for (valueType i = 1; i <= S; ++i) {
        if (undefined[i] && degree[i] != 0) {
            color[i] = 1;
            undefined[i] = false;

            if (!push(i))
                pushZero(i);
        }
    }

    for (valueType i = 1; i <= S; ++i)
        assert(!undefined[i]);

    valueType ans = 0;

    for (valueType i = 1; i <= N; ++i) {
        assert(color[i] == color[now[i]]);
        
        if (color[i] == 0)
            ++ans;
    }

    std::cout << ans << std::endl;
}

void clear() {
    N = M = S = 0;
    color.clear();
    now.clear();
    degree.clear();
    G.clear();
    undefined.clear();
    revG.clear();
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

// #ifndef LOCAL_STDIO
//     freopen("tribool.in", "r", stdin);
//     freopen("tribool.out", "w", stdout);
// #endif

    valueType ID, T;

    std::cin >> ID >> T;

    for (valueType testcase = 0; testcase < T; ++testcase) {
        clear();
        
        solve();
    }

    return 0;
}

[NOIP2023] 双序列拓展

首先考虑一个 \(\mathcal{O}(nm)\) 的 \(\tt{DP}\)，设 \(f_{i, j}\) 表示是否存在方案使得 \(X_i\) 与 \(Y_j\) 配对。那么有转移：

\[f_{i, j} = f_{i - 1, j} \text{ OR } f_{i, j - 1} \text{ OR } f_{i - 1, j - 1} \]

考虑上述的过程在干什么，设 \(X_1 < Y_1\)，那么我们可以构造出一个 \(n \times m\) 的网格 \(A\)，满足 \(A_{i, j} = \left[X_i < Y_j\right]\)。

那么 \(f_{i, j}\) 实质上表示的就是从 \(\left(1, 1\right)\) 只向下，右或右下移动是否可以到达 \(\left(i, j\right)\)。

考虑特殊性质下的方格图，设 \(X_{\min}\) 表示 \(X\) 的最小值，\(X_{\max}\) 表示 \(X\) 的最大值，\(Y_{\min}\) 表示 \(Y\) 的最小值，\(Y_{\max}\) 表示 \(Y\) 的最大值。

那么如果 \(X_{\min} \ge Y_{\min}\) 或者 \(X_{\max} \ge Y_{\max}\)，那么一定无解。

所以有 \(X_{\min} < Y_{\min}, X_{\max} < Y_{\max}\)。

转化到网格图上，可以发现图的最后一行和最后一列的值均为 \(1\)，所以只要可以从 \(\left(1, 1\right)\) 到达最后一行或最后一列的任意一个格子均可以到达 \(\left(n, m\right)\)。发现此时最后一行或最后一列可以视为一个边界。考虑前 \(n - 1\) 行和 \(m - 1\) 列，发现我们可以继续寻找出两个序列的极值并继续收缩边界，直到收缩到第 \(1\) 行或第 \(1\) 列或在中途发现无解。

在没有特殊限制的情况下可以通过序列极值构成的十字架将网格分为四部分，对于左上和右下部分分别处理即可。

Code

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;

namespace MAIN {
    PairVector PreMaxA, PreMinA, SufMaxA, SufMinA;
    PairVector PreMaxB, PreMinB, SufMaxB, SufMinB;

    bool checkUp(valueType X, valueType Y, valueType N, valueType M) {
        if (X == 1 || Y == 1)
            return true;

        auto const &[MinA, MinA_Pos] = PreMinA[X - 1];
        auto const &[MaxA, MaxA_Pos] = PreMaxA[X - 1];
        auto const &[MinB, MinB_Pos] = PreMinB[Y - 1];
        auto const &[MaxB, MaxB_Pos] = PreMaxB[Y - 1];

        if (MinA < MinB)
            return checkUp(MinA_Pos, Y, N, M);

        if (MaxB > MaxA)
            return checkUp(X, MaxB_Pos, N, M);

        return false;
    }

    bool checkDown(valueType X, valueType Y, valueType N, valueType M) {
        if (X == N || Y == M)
            return true;

        auto const &[MinA, MinA_Pos] = SufMinA[X + 1];
        auto const &[MaxA, MaxA_Pos] = SufMaxA[X + 1];
        auto const &[MinB, MinB_Pos] = SufMinB[Y + 1];
        auto const &[MaxB, MaxB_Pos] = SufMaxB[Y + 1];

        if (MinA < MinB)
            return checkDown(MinA_Pos, Y, N, M);

        if (MaxB > MaxA)
            return checkDown(X, MaxB_Pos, N, M);

        return false;
    }

    bool solve(valueType N, valueType M, ValueVector const &A, ValueVector const &B) {
        PreMaxA.clear();
        PreMinA.clear();
        SufMaxA.clear();
        SufMinA.clear();
        PreMaxB.clear();
        PreMinB.clear();
        SufMaxB.clear();
        SufMinB.clear();

        PreMaxA.resize(N + 1);
        PreMinA.resize(N + 1);
        SufMaxA.resize(N + 1);
        SufMinA.resize(N + 1);
        PreMaxB.resize(M + 1);
        PreMinB.resize(M + 1);
        SufMaxB.resize(M + 1);
        SufMinB.resize(M + 1);

        if (A[1] >= B[1])
            return false;

        PreMaxA[1] = ValuePair(A[1], 1);
        PreMinA[1] = ValuePair(A[1], 1);

        for (valueType i = 2; i <= N; ++i) {
            PreMaxA[i] = std::max(PreMaxA[i - 1], ValuePair(A[i], i));
            PreMinA[i] = std::min(PreMinA[i - 1], ValuePair(A[i], i));
        }

        SufMaxA[N] = ValuePair(A[N], N);
        SufMinA[N] = ValuePair(A[N], N);

        for (valueType i = N - 1; i >= 1; --i) {
            SufMaxA[i] = std::max(SufMaxA[i + 1], ValuePair(A[i], i));
            SufMinA[i] = std::min(SufMinA[i + 1], ValuePair(A[i], i));
        }

        PreMaxB[1] = ValuePair(B[1], 1);
        PreMinB[1] = ValuePair(B[1], 1);

        for (valueType i = 2; i <= M; ++i) {
            PreMaxB[i] = std::max(PreMaxB[i - 1], ValuePair(B[i], i));
            PreMinB[i] = std::min(PreMinB[i - 1], ValuePair(B[i], i));
        }

        SufMaxB[M] = ValuePair(B[M], M);
        SufMinB[M] = ValuePair(B[M], M);

        for (valueType i = M - 1; i >= 1; --i) {
            SufMaxB[i] = std::max(SufMaxB[i + 1], ValuePair(B[i], i));
            SufMinB[i] = std::min(SufMinB[i + 1], ValuePair(B[i], i));
        }

        auto const &[MinA, MinA_Pos] = PreMinA[N];
        auto const &[MaxA, MaxA_Pos] = PreMaxA[N];
        auto const &[MinB, MinB_Pos] = PreMinB[M];
        auto const &[MaxB, MaxB_Pos] = PreMaxB[M];

        if (MinA >= MinB || MaxA >= MaxB)
            return false;

        return checkUp(MinA_Pos, MaxB_Pos, N, M) && checkDown(MinA_Pos, MaxB_Pos, N, M);
    }
}// namespace MAIN

using MAIN::solve;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    // #ifndef LOCAL_STDIO
    //     freopen("expand.in", "r", stdin);
    //     freopen("expand.out", "w", stdout);
    // #endif

    valueType ID, N, M, Q;

    std::cin >> ID >> N >> M >> Q;

    ValueVector A(N + 1), B(M + 1);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> A[i];

    for (valueType i = 1; i <= M; ++i)
        std::cin >> B[i];

    std::cout << ((solve(N, M, A, B) || solve(M, N, B, A)) ? 1 : 0);

    for (valueType query = 0; query < Q; ++query) {
        valueType KA, KB;

 

因此对于点
，向 和点 连一条容量为

的边即可。
Code

    [NOIP2023] 三值逻辑
    [NOIP2023] 双序列拓展
    [SDOI2016] 数字配对
    [HNOI2013] 切糕


__EOF__
本文作者： User-Unauthorized
本文链接： https://www.cnblogs.com/User-Unauthorized/p/2023-12-4.html
关于博主： 评论和私信会在第一时间回复。或者直接私信我。
版权声明： 本博客所       std::cin >> KA >> KB;

        ValueVector TA = A, TB = B;

        for (valueType i = 0; i < KA; ++i) {
            valueType x, y;

            std::cin >> x >> y;

            TA[x] = y;
        }

        for (valueType i = 0; i < KB; ++i) {
            valueType x, y;

            std::cin >> x >> y;

            TB[x] = y;
        }

        std::cout << ((solve(N, M, TA, TB) || solve(M, N, TB, TA)) ? 1 : 0);
    }

    std::cout << std::endl;

    return 0;
}

[SDOI2016] 数字配对

对于每个数 \(i\)，设 \(f_i\) 表示 \(a_i\) 的所有质因子的次数之和。那么两个数 \(i, j\) 可以配对当且仅当 \(a_i \mid a_j \land f_j = f_i + 1\) 或 \(a_j \mid a_i \land f_i = f_j + 1\)。

所以 \(f_i\) 奇偶性相同的数之间一定不可能配对，考虑将 \(f_i\) 为奇数的点作为左部点，\(f_i\) 为偶数的点作为右部点，在可以配对的数对之间连边，可以发现形成的网络为一个二分图。

那么接下来问题转化为了如何在获得的价值总和不小于 \(0\) 的前提下求出最大流。

考虑应用最大费用最大流，因为其均为剩余网络中的最长路，因此每轮增广后剩余网络中的最长路单调递减。

因此当前轮增广后的费用为负时退掉一些流使得费用为正后退出即可。

Code

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;

class MCMF {
private:
    struct Edge {
    public:
        typedef std::list<Edge> container;
        typedef container::iterator iterator;

        valueType to;
        valueType cap;
        valueType flow;
        valueType cost;
        iterator pair;

        Edge() : to(-1), cap(-1), flow(-1), cost(0), pair(){};

        Edge(valueType to, valueType cap, valueType c, iterator pair = iterator()) : to(to), cap(cap), flow(0), cost(c),
                                                                                     pair(pair){};
    };

    typedef std::vector<Edge::container> Graph;
    typedef std::vector<Edge::iterator> IterVector;
    typedef std::vector<bool> bitset;

    valueType N;
    Graph G;
    ValueVector dist;
    IterVector start;
    bool Initialized;

public:
    explicit MCMF(valueType N) : N(N), G(N + 1), dist(N + 1, 0), start(N + 1), Initialized(false){};

    Edge::iterator addEdge(valueType from, valueType to, valueType cap, valueType cost) {
        if (__builtin_expect(Initialized, false))
            throw std::runtime_error("MCMF: addEdge after init");

        G[from].emplace_back(to, cap, cost);
        G[to].emplace_back(from, 0, -cost);
        G[from].back().pair = std::prev(G[to].end());
        G[to].back().pair = std::prev(G[from].end());

        return std::prev(G[from].end());
    }

    void init() {
        if (__builtin_expect(Initialized, false))
            throw std::runtime_error("MCMF: init twice");

        Initialized = true;

        std::fill(dist.begin(), dist.end(), 0);

        for (valueType i = 1; i <= N; ++i)
            start[i] = G[i].begin();
    }

    void reset() {
        if (__builtin_expect(!Initialized, false))
            throw std::runtime_error("MCMF: reset before init");

        for (valueType i = 1; i <= N; ++i)
            for (auto &iter : G[i])
                iter.flow = 0;

        std::fill(dist.begin(), dist.end(), 0);

        Initialized = false;
    }

    std::pair<valueType, valueType> maxFlow(valueType S, valueType T) {
        if (__builtin_expect(!Initialized, false))
            throw std::runtime_error("MCMF: maxFlow before init");

        std::pair<valueType, valueType> result(0, 0);

        while (bfs(S, T)) {
            IterVector begin = start;
            
            bitset visited(N + 1, false);

            valueType const flow = dfs(S, T, std::numeric_limits<valueType>::max(), begin, visited);
            
            if (result.second + flow * dist[T] < 0) {
                result.first += -result.second / dist[T];
                result.second += result.second / dist[T] * dist[T];

                break;
            }

            result.first += flow;
            result.second += flow * dist[T];
        }

        return result;
    }

private:
    bool bfs(valueType S, valueType T) {
        std::fill(dist.begin(), dist.end(), std::numeric_limits<valueType>::min() >> 5);

        bitset visited(N + 1, false);

        std::queue<valueType> Q;

        Q.push(S);
        dist[S] = 0;
        visited[S] = true;

        while (!Q.empty()) {
            valueType const u = Q.front();

            visited[u] = false;
            Q.pop();

            for (auto const &e : G[u]) {
                if ((e.cap > e.flow) && (dist[e.to] < dist[u] + e.cost)) {
                    dist[e.to] = dist[u] + e.cost;

                    if (!visited[e.to]) {
                        Q.push(e.to);
                        visited[e.to] = true;
                    }
                }
            }
        }

        return dist[T] != (std::numeric_limits<valueType>::min() >> 5);
    }

    valueType dfs(valueType u, valueType T, valueType flow, IterVector &Begin, bitset &visited) {
        if (u == T || flow == 0)
            return flow;

        valueType result = 0;

        visited[u] = true;

        for (auto &e = Begin[u]; e != G[u].end() && flow > 0; ++e) {
            if (!visited[e->to] && e->cap > e->flow && dist[e->to] == dist[u] + e->cost) {
                valueType const f = dfs(e->to, T, std::min(flow - result, e->cap - e->flow), Begin, visited);

                if (f == 0) {
                    dist[e->to] = std::numeric_limits<valueType>::min();

                    continue;
                }

                e->flow += f;
                e->pair->flow -= f;

                result += f;

                if (result == flow) {
                    visited[u] = false;

                    return flow;
                }
            }
        }

        visited[u] = false;

        return result;
    }
};

constexpr valueType INF = std::numeric_limits<valueType>::max();

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N;

    std::cin >> N;

    valueType const S = N + 1, T = N + 2;

    MCMF mcmf(N + 3);

    ValueVector A(N + 1), B(N + 1), C(N + 1), count(N + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> A[i];

    for (valueType i = 1; i <= N; ++i)
        std::cin >> B[i];

    for (valueType i = 1; i <= N; ++i)
        std::cin >> C[i];

    for (valueType i = 1; i <= N; ++i) {
        valueType x = A[i];

        for (valueType j = 2; j * j <= x; ++j) {
            while (x % j == 0) {
                x /= j;

                ++count[i];
            }
        }

        if (x > 1)
            ++count[i];
    }

    for (valueType i = 1; i <= N; ++i) {
        if ((count[i] & 1) == 1)
            mcmf.addEdge(S, i, B[i], 0);
        else
            mcmf.addEdge(i, T, B[i], 0);
    }

    for (valueType i = 1; i <= N; ++i) {
        if ((count[i] & 1) == 0)
            continue;

        for (valueType j = 1; j <= N; ++j)
            if ((A[i] % A[j] == 0 && count[i] == count[j] + 1) || (A[j] % A[i] == 0 && count[j] == count[i] + 1))
                mcmf.addEdge(i, j, INF, C[i] * C[j]);
    }

    mcmf.init();

    auto const ans = mcmf.maxFlow(S, T);

    std::cout << ans.first << std::endl;

    return 0;
}

[HNOI2013] 切糕

可以发现切面会把点分为两个集合，故考虑最小割。

发现可以从点 \(\left(x, y, z\right)\) 向 \(\left(x, y, z + 1\right)\) 连边，流量为 \(v\left(x, y, z\right)\)。其中 \(\left(x, y, 0\right) = S, v\left(x, y, 0\right) = \infty, \left(x, y, R + 1\right) = T\)

那么可以发现 \(S\) 集合意味着切面及以下的点的集合，\(T\) 集合意味着切面以上的点的集合，考虑如何处理相邻切面距离不能超过 \(D\) 的限制。

发现对于相邻的竖柱 \(a, b\)，设 \(\left(a, x\right)\) 表示竖柱 \(a\) 上的第 \(x\) 层对应的节点。那么限制可以表示为

\[\forall (a, x) \in S, (b, x - D) \in S \]

因此对于点 \(\left(x, y, z\right)\)，向 \(\left(x \pm 1, y, z - D\right)\) 和点 \(\left(x, y \pm 1, z - D\right)\) 连一条容量为 \(\infty\) 的边即可。

Code

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<ValueMatrix> ValueCube;

class Dinic {
private:
    struct Edge {
    public:
        typedef std::list<Edge> container;
        typedef container::iterator iterator;

        valueType to;
        valueType cap;
        valueType flow;
        iterator pair;

        Edge() : to(-1), cap(-1), flow(-1), pair(){};

        Edge(valueType to, valueType cap, iterator pair = iterator()) : to(to), cap(cap), flow(0), pair(pair){};
    };

    typedef std::vector<Edge::container> Graph;
    typedef std::vector<Edge::iterator> IterVector;

    valueType N;
    Graph G;
    ValueVector depth;
    IterVector start;
    bool Initialized;

public:
    explicit Dinic(valueType N) : N(N), G(N + 1), depth(N + 1, 0), start(N + 1), Initialized(false){};

    void addEdge(valueType from, valueType to, valueType cap) {
        if (__builtin_expect(Initialized, false))
            throw std::runtime_error("Dinic: addEdge after init");

        G[from].emplace_back(to, cap);
        G[to].emplace_back(from, 0);
        G[from].back().pair = std::prev(G[to].end());
        G[to].back().pair = std::prev(G[from].end());
    }

    void init() {
        if (__builtin_expect(Initialized, false))
            throw std::runtime_error("Dinic: init twice");

        Initialized = true;

        std::fill(depth.begin(), depth.end(), 0);

        for (valueType i = 1; i <= N; ++i)
            start[i] = G[i].begin();
    }

    void reset() {
        if (__builtin_expect(!Initialized, false))
            throw std::runtime_error("Dinic: reset before init");

        for (valueType i = 1; i <= N; ++i)
            for (auto &iter : G[i])
                iter.flow = 0;

        std::fill(depth.begin(), depth.end(), 0);

        Initialized = false;
    }

    valueType maxFlow(valueType S, valueType T) {
        if (__builtin_expect(!Initialized, false))
            throw std::runtime_error("Dinic: maxFlow before init");

        valueType result = 0;

        while (bfs(S, T)) {
            IterVector begin = start;

            result += dfs(S, T, std::numeric_limits<valueType>::max(), begin);
        }

        return result;
    }

private:
    bool bfs(valueType S, valueType T) {
        std::fill(depth.begin(), depth.end(), 0);

        std::queue<valueType> Q;

        Q.push(S);
        depth[S] = 1;

        while (!Q.empty()) {
            valueType const u = Q.front();

            Q.pop();

            for (auto const &e : G[u]) {
                if ((e.cap > e.flow) && (!depth[e.to])) {
                    depth[e.to] = depth[u] + 1;
                    Q.push(e.to);
                }
            }
        }

        return depth[T] > 0;
    }

    valueType dfs(valueType u, valueType T, valueType flow, IterVector &Begin) {
        if (u == T || flow == 0)
            return flow;

        valueType result = 0;

        for (auto &e = Begin[u]; e != G[u].end(); ++e) {
            if (e->cap > e->flow && depth[e->to] == depth[u] + 1) {
                valueType const f = dfs(e->to, T, std::min(flow - result, e->cap - e->flow), Begin);

                e->flow += f;
                e->pair->flow -= f;

                result += f;

                if (result == flow)
                    return flow;
            }
        }

        return result;
    }
};

constexpr valueType INF = std::numeric_limits<valueType>::max();

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType P, Q, R, D;

    std::cin >> P >> Q >> R >> D;

    valueType size = 0;

    valueType const S = ++size, T = ++size;

    ValueCube ID(P + 1, ValueMatrix(Q + 1, ValueVector(R + 2, 0))), W(P + 1, ValueMatrix(Q + 1, ValueVector(R + 1, INF)));

    for (valueType i = 1; i <= P; ++i) {
        for (valueType j = 1; j <= Q; ++j) {
            for (valueType k = 1; k <= R; ++k)
                ID[i][j][k] = ++size;

            ID[i][j][0] = S;
            ID[i][j][R + 1] = T;
        }
    }

    for (valueType k = 1; k <= R; ++k)
        for (valueType i = 1; i <= P; ++i)
            for (valueType j = 1; j <= Q; ++j)
                std::cin >> W[i][j][k];

    Dinic dinic(size);

    for (valueType i = 1; i <= P; ++i)
        for (valueType j = 1; j <= Q; ++j)
            for (valueType k = 0; k <= R; ++k)
                dinic.addEdge(ID[i][j][k], ID[i][j][k + 1], W[i][j][k]);

    for (valueType i = 1; i <= P; ++i) {
        for (valueType j = 1; j <= Q; ++j) {
            for (valueType k = D; k <= R; ++k) {
                if (i > 1)
                    dinic.addEdge(ID[i][j][k], ID[i - 1][j][k - D], INF);
                
                if (i < P)
                    dinic.addEdge(ID[i][j][k], ID[i + 1][j][k - D], INF);

                if (j > 1)
                    dinic.addEdge(ID[i][j][k], ID[i][j - 1][k - D], INF);

                if (j < Q)
                    dinic.addEdge(ID[i][j][k], ID[i][j + 1][k - D], INF);
            }
        }
    }

    dinic.init();

    std::cout << dinic.maxFlow(S, T) << std::endl;

    return 0;
}

标签：std,typedef,Set,const,2023.12,valueType,flow,Solution,false
From： https://www.cnblogs.com/User-Unauthorized/p/2023-12-4.html

[NOIP2023] 三值逻辑

[NOIP2023] 双序列拓展

[SDOI2016] 数字配对

[HNOI2013] 切糕

相关文章

赞助商

阅读排行