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.
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