Editorial for Bedao Grand Contest 15 - Lomkdle


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
#include <bits/stdc++.h>
using namespace std;    

using ll = long long;
using ld = long double;

template<class T>
struct flow_network{
    int n;
    vector<vector<int>> adj;
    struct E{
        int from, to;
        T capacity, flow;
    };
    vector<E> edge;
    flow_network(int n): n(n), adj(n){ }
    void clear_flow(){
        for(auto &e: edge) e.flow = 0;
    }
    int link(int from, int to, T cap){
        int ind = (int)edge.size();
        adj[from].push_back(ind);
        edge.push_back({from, to, cap, 0});
        adj[to].push_back(ind + 1);
        edge.push_back({to, from, cap, 0});
        return ind;
    }
    int orient(int from, int to, T cap){
        int ind = (int)edge.size();
        adj[from].push_back(ind);
        edge.push_back({from, to, cap, 0});
        adj[to].push_back(ind + 1);
        edge.push_back({to, from, 0, 0});
        return ind;
    }
    void add_flow(int i, T f){
        edge[i].flow += f;
        edge[i ^ 1].flow -= f;
    }
    friend ostream &operator<<(ostream &out, const flow_network &F){
        out << "\n";
        for(auto &e: F.edge){
            out << "{" << e.from << " -> " << e.to << ", " << e.flow << "/" << e.capacity << "}\n";
        }
        return out;
    }
};

// Requires flow_network
template<class T>
struct dinic_maximum_flow{
    static constexpr T eps = (T)1e-9, inf = numeric_limits<T>::max();
    flow_network<T> &F;
    dinic_maximum_flow(flow_network<T> &F): F(F), ptr(F.n), level(F.n), q(F.n){ }
    vector<int> ptr, level, q;
    bool bfs(int source, int sink){
        fill(level.begin(), level.end(), -1);
        q[0] = sink;
        level[sink] = 0;
        for(auto beg = 0, end = 1; beg < end; ){
            int i = q[beg ++];
            for(auto ind: F.adj[i]){
                auto &e = F.edge[ind];
                auto &re = F.edge[ind ^ 1];
                if(re.capacity - re.flow > eps && level[e.to] == -1){
                    level[e.to] = level[i] + 1;
                    if(e.to == source) return true;
                    q[end ++] = e.to;
                }
            }
        }
        return false;
    }
    T dfs(int u, T w, int sink){
        if(u == sink) return w;
        int &j = ptr[u];
        while(j >= 0){
            int ind = F.adj[u][j];
            auto &e = F.edge[ind];
            if(e.capacity - e.flow > eps && level[e.to] == level[u] - 1){
                T flow = dfs(e.to, min(e.capacity - e.flow, w), sink);
                if(flow > eps){
                    F.add_flow(ind, flow);
                    return flow;
                }
            }
            -- j;
        }
        return 0;
    }
    // Find a maximum source-sink flow
    // O(V^2 E) ( O(E min(V^2/3, E^1/2)) for unit network )
    T maximum_flow(int source, int sink){
        assert(0 <= source && source < F.n && 0 <= sink && sink < F.n);
        T flow = 0;
        while(bfs(source, sink)){
            for(auto i = 0; i < F.n; ++ i) ptr[i] = (int)F.adj[i].size() - 1;
            T sum = 0;
            while(true){
                T add = dfs(source, inf, sink);
                if(add <= eps) break;
                sum += add;
            }
            if(sum <= eps) break;
            flow += sum;
        }
        return flow;
    }
    // Find a minimum source-sink cut
    // O(V^2 E) ( O(E min(V^2/3, E^1/2)) for unit network )
    tuple<T, vector<int>, vector<int>> minimum_cut(int source, int sink){
        T cut_weight = maximum_flow(source, sink);
        vector<int> left, right;
        for(auto u = 0; u < F.n; ++ u) (!~level[u] ? left : right).push_back(u);
        return {cut_weight, left, right};
    }
};

// Requires flow_network
template<class T, class Flow_Solver>
struct flow_network_with_demand{
    flow_network_with_demand(int n): n(n), F(n + 2), D(F), demand(n){}
    int orient(int u, int v, T d, T c){
        assert(0 <= d && d <= c);
        ++ m;
        int id = F.orient(u, v, c - d);
        demand[u] -= d;
        demand[v] += d;
        edge_id.push_back(id);
        edge_demand.push_back(d);
        return id;
    }
    T _setup(){
        T req = 0;
        for(auto u = 0; u < n; ++ u){
            if(demand[u] > 0) F.orient(n, u, demand[u]), req += demand[u];
            else if(demand[u] < 0) F.orient(u, n + 1, -demand[u]);
        }
        return req;
    }
    // Destroys the network after getting called
    optional<vector<T>> feasible_circulation(){
        vector<T> w = edge_demand;
        T req = _setup();
        if(req != D.maximum_flow(n, n + 1)) return {};
        for(auto i = 0; i < m; ++ i) w[i] += F.edge[edge_id[i]].flow;
        return w;
    }
    // Destroys the network after getting called
    optional<pair<T, vector<T>>> feasible_flow(int s, int t){
        assert(0 <= min(s, t) && max(s, t) < n && s != t);
        int id = F.orient(t, s, numeric_limits<T>::max());
        auto resptr = feasible_circulation();
        if(!resptr) return {};
        return pair{F.edge[id].flow, *resptr};
    }
    // Destroys the network after getting called
    optional<pair<T, vector<T>>> maximum_feasible_flow(int s, int t){
        assert(0 <= min(s, t) && max(s, t) < n && s != t);
        int id = F.orient(t, s, numeric_limits<T>::max());
        auto resptr = feasible_circulation();
        if(!resptr) return {};
        auto w = edge_demand;
        T flow = F.edge[id].flow;
        F.edge[id].capacity = F.edge[id].flow = F.edge[id ^ 1].flow = 0;
        flow += D.maximum_flow(s, t);
        for(auto i = 0; i < m; ++ i) w[i] += F.edge[edge_id[i]].flow;
        return pair{flow, w};
    }
    // Destroys the network after getting called
    optional<pair<T, vector<T>>> minimum_feasible_flow(int s, int t){
        assert(0 <= min(s, t) && max(s, t) < n && s != t);
        int id = F.orient(t, s, numeric_limits<T>::max());
        auto resptr = feasible_circulation();
        if(!resptr) return {};
        auto w = edge_demand;
        T flow = F.edge[id].flow;
        F.edge[id].capacity = F.edge[id].flow = F.edge[id ^ 1].flow = 0;
        flow -= D.maximum_flow(t, s);
        for(auto i = 0; i < m; ++ i) w[i] += F.edge[edge_id[i]].flow;
        return pair{flow, w};
    }
    int n, m = 0;
    flow_network<T> F;
    Flow_Solver D;
    vector<T> demand;
    vector<int> edge_id;
    vector<T> edge_demand;
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    constexpr int C = 26;

int tests; cin >> tests; while (tests--){
    int n, m;
    cin >> n >> m;

    vector <string> a(m), b(m);
    for (int i = 0; i < m; i++){
        cin >> a[i] >> b[i];
    }

    flow_network_with_demand <int, dinic_maximum_flow <int>> fn(1 + C + n + 1);
    int source = fn.n - 2, sink = fn.n - 1;

    vector <pair <int, int>> lhs(C, pair{0, n}), rhs(n, pair{1, 1});
    vector <vector <pair <int, int>>> mid(C, vector <pair <int, int>>(n, pair{0, 1}));
    for (int i = 0; i < m; i++){
        array <int, C> cntGY;
        cntGY.fill(0);
        array <bool, C> hasB;
        hasB.fill(false);
        for (int j = 0; j < n; j++){
            if (b[i][j] == 'B'){
                hasB[a[i][j] - 'A'] = true;
                mid[a[i][j] - 'A'][j] = pair{0, 0};
            }
            else if (b[i][j] == 'G'){
                cntGY[a[i][j] - 'A']++;
                mid[a[i][j] - 'A'][j] = pair{1, 1};
            }
            else{
                cntGY[a[i][j] - 'A']++;
                mid[a[i][j] - 'A'][j] = pair{0, 0};
            }
        }
        for (int c = 0; c < C; c++){
            if (hasB[c]){
                lhs[c] = pair{cntGY[c], cntGY[c]};
                continue;
            }
            lhs[c].first = max(lhs[c].first, cntGY[c]);
        }
    }

    for (int c = 0; c < C; c++){
        fn.orient(source, c, lhs[c].first, lhs[c].second);
    }
    for (int c = 0; c < C; c++){
        for (int j = 0; j < n; j++){
            fn.orient(c, C + j, mid[c][j].first, mid[c][j].second);
        }
    }
    for (int j = 0; j < n; j++){
        fn.orient(C + j, sink, rhs[j].first, rhs[j].second);
    }

    string ans(n, '?');
    auto [flow, w] = fn.maximum_feasible_flow(source, sink).value();
    assert(flow == n);
    for (int i = 0; i < ssize(w); i++){
        auto id = fn.edge_id[i];
        auto e = fn.F.edge[id];
        int u = e.from, v = e.to;
        if (0 <= u and u < C and C <= v and v < C + n){
            if (w[i] == 1){
                ans[v - C] = char(u + 'A');
            }
        }
    }
    cout << ans << "\n";
}
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.