Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <type_traits>
- using namespace std;
- /*MACROS*/
- //FUNCTIONS
- #define in_range(i, l, r) for(ll i = l; i < r; i++)
- #define all(v) begin(v), end(v)
- #define rall(v) (v).rbegin(), (v).rend()
- //#define tr(it, container) for(auto it = begin(container); it != end(container); it++)
- #define rtr(it, container) for(auto it = (container).rbegin(); it != (container).rend(); it++)
- #define present(element, container) ((container).find(element) != end(container))
- #define _T(...) __VA_ARGS__
- #define forever() for(;;)
- //ABBREVIATIONS
- #define sz(c) (ll(c.size()))
- #define pb push_back
- #define fst first
- #define scd second
- #define cmpBy(T, field) [](const T& x, const T& y){ return x.field < y.field; }
- template<class T> T peek(queue<T>& q) { T top_el = q.front(); q.pop(); return top_el; }
- //TYPE SAFETY
- #define sqrt(x) sqrt(1.0*(x))
- #define pow(x, n) pow(1.0*(x), n)
- //CONSTANTS
- #define INF (numeric_limits<int>::max())
- #define MINF (numeric_limits<int>::min())
- #define LINF (numeric_limits<long long>::max())
- #define LMINF (numeric_limits<long long>::min())
- #define EPS (1E-9)
- #define PI ((long double)3.1415926535897932384626433832795028841971693993751)
- #define reunique(container) ((container).resize(unique(all(container))-begin(container)))
- /*TYPES*/
- typedef unsigned long long ull;
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- typedef long double ld;
- //STL INPUT
- void fastIO(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); }
- template<class T1, class T2> istream& operator >>(istream& in, pair<T1, T2>& P){in >> P.fst >> P.scd; return in;}
- template<class T> istream& operator >>(istream& in, vector<T>& Col){for(auto &el : Col) in >> el; return in;}
- template<class T> inline void getarr(T* arr, size_t l, size_t r) { in_range(i, l, r) std::cin >> arr[i]; }
- //STL OUTPUT
- template<class T1, class T2> ostream& operator <<(ostream& os, const pair<T1, T2>& p){os << "(" << p.fst << ", " << p.scd << ")"; return os;}
- template<class T> ostream& operator <<(ostream& os, const vector<vector<T>>& v){for(auto &row : v){ for(auto &el : row) os << el << " "; os << "\n";} return os;}
- template<class T> ostream& operator <<(ostream& os, const vector<T>& Col){for(auto &el : Col) os << el << " "; return os;}
- template<class T> ostream& operator <<(ostream& os, const std::set<T>& Col){for(auto &el : Col) os << el << " "; return os;}
- template<class T1, class T2> ostream& operator <<(ostream& os, const map<T1, T2>& Col){for(auto &el : Col) os << el << " "; return os;}
- template<class T> inline void printarr(T* arr, size_t l, size_t r) { in_range(i, l, r) {std::cout << arr[i] << " ";}; std::cout << "\n"; }
- template<typename T>
- class edge{
- public:
- int from, to;
- int next;
- T f, c;
- template <typename>
- friend ostream& operator <<(ostream&, const edge&);
- };
- template<typename T>
- ostream& operator<<(ostream& out, const edge<T> &e) {
- out << "[" << e.from << " -> " << e.to << ", " << e.f << "\\" << e.c << "]";
- return out;
- }
- template<typename T>
- class solver {
- int n, m;
- int s, t;
- int males, females;
- vector<vector<int>> G;
- vector<edge<T>> edges;
- vector<int> head;
- vector<int> used;
- void add_edge(int a, int b, T c) {
- edges.pb({a, b, head[a], 0, c});
- edges.pb({b, a, head[b], 0, 0});
- head[a] = sz(edges)-2;
- head[b] = sz(edges)-1;
- }
- void read_network() {
- cin >> males >> females;
- for (int i = 0; i < males + 1; ++i) {
- G.push_back(vector<int>(females + 1, 0));
- }
- for (int i = 1, f_id; i <= males; ++i) {
- cin >> f_id;
- for (; f_id != 0; cin >> f_id) {
- G[i][f_id] = 1;
- }
- }
- s = 0, t = males + females + 1;
- head = vector<int>(t + 1, -1);
- for (int i = 1; i <= males; ++i) {
- add_edge(s, i, 1);
- }
- for (int i = 1; i <= females; ++i) {
- add_edge(males + i, t, 1);
- }
- for (int i = 1; i <= males; ++i) {
- for (int j = 1; j <= females; ++j) {
- if (!G[i][j]) {
- add_edge(i, males + j, INF);
- // add_edge(males + j, i, INF);
- }
- }
- }
- n = t + 1;
- m = sz(edges);
- // for (auto e : edges) {
- // cout << e << "\n";
- // }
- }
- vector<T> d;
- vector<int> ptr, q;
- bool bfs() {
- fill(all(d), numeric_limits<T>::max());
- int qh = 0, qt = 0;
- q[qt++] = s;
- d[s] = 0;
- while (qh < qt) {
- int v = q[qh++];
- for (int i = head[v]; i != -1; i = edges[i].next) {
- edge<T> &e = edges[i];
- if (e.f < e.c && d[e.to] > d[v]+1) {
- d[e.to] = d[v]+1;
- q[qt++] = e.to;
- }
- }
- }
- copy(all(head), begin(ptr));
- return d[t] < numeric_limits<T>::max();
- }
- T push(int v, T f) {
- if (v == t || !f) return f;
- for (int &i = ptr[v]; i != -1; i = edges[i].next) {
- edge<T> &e = edges[i];
- if (d[e.to] != d[v]+1) continue;
- if (int pushed = push(e.to, min(f, e.c-e.f))) {
- e.f += pushed, edges[i^1].f -= pushed;
- return pushed;
- }
- }
- return 0;
- }
- void dfs(int u, int from_matching = 0) {
- // cout << "IN DFS: " << u << endl;
- used[u] = true;
- for (int &i = ptr[u]; i != -1; i = edges[i].next) {
- edge<T>& e = edges[i];
- if (e.to == s || e.to == t) continue;
- // cout << e << endl;
- if (!used[e.to] && ((e.f == 1 || edges[i^1].f == 1) ^ !from_matching)) {
- dfs(e.to, from_matching ^ 1);
- }
- }
- }
- public:
- void output_biclique() {
- read_network();
- d = vector<T>(n);
- ptr = q = vector<int>(n);
- T F = 0;
- while (bfs()) {
- while (T pushed = push(s, numeric_limits<T>::max())) {
- F += pushed;
- }
- }
- // cout << "MATHCING SIZE: " << F << endl;
- // всё-таки после поиска макс. паросочетания
- // найти непосредственно рёбра, образующие паросочетание
- vector<edge<T>> matching;
- for (auto e : edges) {
- if (e.c == INF && e.f == 1) {
- matching.push_back(e);
- }
- }
- // построить по ним минимальное вершинное покрытие
- // (как искать альтернированные пути?)
- // нужно вспомнить, что есть такой массив как head
- // в котором хранятся рёбра, исходящие из данной вершины
- // для каждого из них легко проверить, лежит ли оно в паросочетании или нет
- // значит, найти альтернирующий путь очень легко
- // cout << "MAXIMAL MATCHING: ";
- // for (auto e : matching) { cout << e << "\n"; }
- // cout << "\n";
- copy(all(head), begin(ptr));
- used.assign(n, false);
- vector<int> in_matching(n, false);
- for (auto e : matching) { in_matching[e.from] = true; }
- // cout << "1 FOR MALE IN MATCHING: " << in_matching << endl;
- for (int i = 1; i <= males; ++i) {
- if (!in_matching[i]) {
- dfs(i);
- }
- }
- // cout << "1 FOR REACHABLE BY ALTERNATING PATHS: " << used << endl;
- for (int i = 1; i <= males; ++i) { used[i] ^= 1; }
- // cout << "1 FOR BEING IN A VERTEX COVER: " << used << endl;
- for (int i = 1; i <= males + females; ++i) { used[i] ^= 1; }
- // cout << "1 FOR BEING IN MAX INDEPENDENT SET: " << used << endl;
- vector<int> m_inv, f_inv;
- for (int i = 1; i <= males; ++i) {
- if (used[i]) {
- m_inv.push_back(i);
- }
- }
- for (int i = males + 1; i <= males + females; ++i) {
- if (used[i]) {
- f_inv.push_back(i - males);
- }
- }
- cout << sz(m_inv) + sz(f_inv) << "\n";
- cout << sz(m_inv) << " " << sz(f_inv) << "\n";
- cout << m_inv << "\n" << f_inv << endl;
- }
- };
- int main() {
- // ios::sync_with_stdio(false);
- // std::cin.tie(0);
- // freopen("in", "r", stdin);
- // freopen("out", "w", stdout);
- int k; cin >> k;
- while (k--) {
- auto s = solver<int>();
- s.output_biclique();
- cout << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment