Guest User

Birthday

a guest
Sep 30th, 2017
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.81 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <type_traits>
  3. using namespace std;
  4.  
  5. /*MACROS*/
  6. //FUNCTIONS
  7. #define in_range(i, l, r) for(ll i = l; i < r; i++)
  8.  
  9. #define all(v) begin(v), end(v)
  10. #define rall(v) (v).rbegin(), (v).rend()
  11.  
  12. //#define tr(it, container) for(auto it = begin(container); it != end(container); it++)
  13. #define rtr(it, container) for(auto it = (container).rbegin(); it != (container).rend(); it++)
  14.  
  15. #define present(element, container) ((container).find(element) != end(container))
  16.  
  17. #define _T(...) __VA_ARGS__
  18. #define forever() for(;;)
  19.  
  20. //ABBREVIATIONS
  21. #define sz(c) (ll(c.size()))
  22. #define pb push_back
  23. #define fst first
  24. #define scd second
  25. #define cmpBy(T, field) [](const T& x, const T& y){ return x.field < y.field; }
  26. template<class T> T peek(queue<T>& q) { T top_el = q.front(); q.pop(); return top_el; }
  27.  
  28. //TYPE SAFETY
  29. #define sqrt(x) sqrt(1.0*(x))
  30. #define pow(x, n) pow(1.0*(x), n)
  31.  
  32. //CONSTANTS
  33. #define INF (numeric_limits<int>::max())
  34. #define MINF (numeric_limits<int>::min())
  35. #define LINF (numeric_limits<long long>::max())
  36. #define LMINF (numeric_limits<long long>::min())
  37. #define EPS (1E-9)
  38. #define PI ((long double)3.1415926535897932384626433832795028841971693993751)
  39.  
  40. #define reunique(container) ((container).resize(unique(all(container))-begin(container)))
  41.  
  42. /*TYPES*/
  43. typedef unsigned long long ull;
  44. typedef long long ll;
  45. typedef pair<int, int> pii;
  46. typedef pair<ll, ll> pll;
  47. typedef long double ld;
  48.  
  49. //STL INPUT
  50. void fastIO(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); }
  51. template<class T1, class T2> istream& operator >>(istream& in, pair<T1, T2>& P){in >> P.fst >> P.scd; return in;}
  52. template<class T> istream& operator >>(istream& in, vector<T>& Col){for(auto &el : Col) in >> el; return in;}
  53. template<class T> inline void getarr(T* arr, size_t l, size_t r) { in_range(i, l, r) std::cin >> arr[i]; }
  54.  
  55. //STL OUTPUT
  56. template<class T1, class T2> ostream& operator <<(ostream& os, const pair<T1, T2>& p){os << "(" << p.fst << ", " << p.scd << ")"; return os;}
  57. 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;}
  58. template<class T> ostream& operator <<(ostream& os, const vector<T>& Col){for(auto &el : Col) os << el << " "; return os;}
  59. template<class T> ostream& operator <<(ostream& os, const std::set<T>& Col){for(auto &el : Col) os << el << " "; return os;}
  60. template<class T1, class T2> ostream& operator <<(ostream& os, const map<T1, T2>& Col){for(auto &el : Col) os << el << " "; return os;}
  61. 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"; }
  62.  
  63. template<typename T>
  64. class edge{
  65. public:
  66.     int from, to;
  67.     int next;
  68.     T f, c;
  69.     template <typename>
  70.     friend ostream& operator <<(ostream&, const edge&);
  71. };
  72.  
  73. template<typename T>
  74. ostream& operator<<(ostream& out, const edge<T> &e) {
  75.     out << "[" << e.from << " -> " << e.to << ", " << e.f << "\\" << e.c << "]";
  76.     return out;
  77. }
  78.  
  79. template<typename T>
  80. class solver {
  81.  
  82.     int n, m;
  83.     int s, t;
  84.     int males, females;
  85.     vector<vector<int>> G;
  86.     vector<edge<T>> edges;
  87.     vector<int> head;
  88.     vector<int> used;
  89.  
  90.     void add_edge(int a, int b, T c) {
  91.         edges.pb({a, b, head[a], 0, c});
  92.         edges.pb({b, a, head[b], 0, 0});
  93.         head[a] = sz(edges)-2;
  94.         head[b] = sz(edges)-1;
  95.     }
  96.  
  97.     void read_network() {
  98.         cin >> males >> females;
  99.         for (int i = 0; i < males + 1; ++i) {
  100.             G.push_back(vector<int>(females + 1, 0));
  101.         }
  102.  
  103.         for (int i = 1, f_id; i <= males; ++i) {
  104.             cin >> f_id;
  105.             for (; f_id != 0; cin >> f_id) {
  106.                 G[i][f_id] = 1;
  107.             }
  108.         }
  109.  
  110.         s = 0, t = males + females + 1;
  111.         head = vector<int>(t + 1, -1);
  112.         for (int i = 1; i <= males; ++i) {
  113.             add_edge(s, i, 1);
  114.         }
  115.         for (int i = 1; i <= females; ++i) {
  116.             add_edge(males + i, t, 1);
  117.         }
  118.         for (int i = 1; i <= males; ++i) {
  119.             for (int j = 1; j <= females; ++j) {
  120.                 if (!G[i][j]) {
  121.                     add_edge(i, males + j, INF);
  122. //                    add_edge(males + j, i, INF);
  123.                 }
  124.             }
  125.         }
  126.         n = t + 1;
  127.         m = sz(edges);
  128. //        for (auto e : edges) {
  129. //            cout << e << "\n";
  130. //        }
  131.     }
  132.  
  133.     vector<T> d;
  134.     vector<int> ptr, q;
  135.     bool bfs() {
  136.         fill(all(d), numeric_limits<T>::max());
  137.         int qh = 0, qt = 0;
  138.         q[qt++] = s;
  139.         d[s] = 0;
  140.         while (qh < qt) {
  141.             int v = q[qh++];
  142.             for (int i = head[v]; i != -1; i = edges[i].next) {
  143.                 edge<T> &e = edges[i];
  144.                 if (e.f < e.c && d[e.to] > d[v]+1) {
  145.                     d[e.to] = d[v]+1;
  146.                     q[qt++] = e.to;
  147.                 }
  148.             }
  149.         }
  150.         copy(all(head), begin(ptr));
  151.         return d[t] < numeric_limits<T>::max();
  152.     }
  153.  
  154.     T push(int v, T f) {
  155.         if (v == t || !f) return f;
  156.         for (int &i = ptr[v]; i != -1; i = edges[i].next) {
  157.             edge<T> &e = edges[i];
  158.             if (d[e.to] != d[v]+1) continue;
  159.             if (int pushed = push(e.to, min(f, e.c-e.f))) {
  160.                 e.f += pushed, edges[i^1].f -= pushed;
  161.                 return pushed;
  162.             }
  163.         }
  164.         return 0;
  165.     }
  166.  
  167.     void dfs(int u, int from_matching = 0) {
  168. //        cout << "IN DFS: " << u << endl;
  169.         used[u] = true;
  170.         for (int &i = ptr[u]; i != -1; i = edges[i].next) {
  171.             edge<T>& e = edges[i];
  172.             if (e.to == s || e.to == t) continue;
  173. //            cout << e << endl;
  174.             if (!used[e.to] && ((e.f == 1 || edges[i^1].f == 1) ^ !from_matching)) {
  175.                 dfs(e.to, from_matching ^ 1);
  176.             }
  177.         }
  178.     }
  179.  
  180. public:
  181.     void output_biclique() {
  182.         read_network();
  183.         d = vector<T>(n);
  184.         ptr = q = vector<int>(n);
  185.         T F = 0;
  186.         while (bfs()) {
  187.             while (T pushed = push(s, numeric_limits<T>::max())) {
  188.                 F += pushed;
  189.             }
  190.         }
  191.  
  192. //        cout << "MATHCING SIZE: " << F << endl;
  193.         // всё-таки после поиска макс. паросочетания
  194.  
  195.  
  196.         // найти непосредственно рёбра, образующие паросочетание
  197.         vector<edge<T>> matching;
  198.         for (auto e : edges) {
  199.             if (e.c == INF && e.f == 1) {
  200.                 matching.push_back(e);
  201.             }
  202.         }
  203.         // построить по ним минимальное вершинное покрытие
  204.         // (как искать альтернированные пути?)
  205.         // нужно вспомнить, что есть такой массив как head
  206.         // в котором хранятся рёбра, исходящие из данной вершины
  207.         // для каждого из них легко проверить, лежит ли оно в паросочетании или нет
  208.         // значит, найти альтернирующий путь очень легко
  209.  
  210. //        cout << "MAXIMAL MATCHING: ";
  211. //        for (auto e : matching) { cout << e << "\n"; }
  212. //        cout << "\n";
  213.  
  214.         copy(all(head), begin(ptr));
  215.         used.assign(n, false);
  216.         vector<int> in_matching(n, false);
  217.  
  218.         for (auto e : matching) { in_matching[e.from] = true; }
  219. //        cout << "1 FOR MALE IN MATCHING: " << in_matching << endl;
  220.         for (int i = 1; i <= males; ++i) {
  221.             if (!in_matching[i]) {
  222.                 dfs(i);
  223.             }
  224.         }
  225. //        cout << "1 FOR REACHABLE BY ALTERNATING PATHS: " << used << endl;
  226.         for (int i = 1; i <= males; ++i) { used[i] ^= 1; }
  227. //        cout << "1 FOR BEING IN A VERTEX COVER: " << used << endl;
  228.         for (int i = 1; i <= males + females; ++i) { used[i] ^= 1; }
  229. //        cout << "1 FOR BEING IN MAX INDEPENDENT SET: " << used << endl;
  230.         vector<int> m_inv, f_inv;
  231.         for (int i = 1; i <= males; ++i) {
  232.             if (used[i]) {
  233.                 m_inv.push_back(i);
  234.             }
  235.         }
  236.         for (int i = males + 1; i <= males + females; ++i) {
  237.             if (used[i]) {
  238.                 f_inv.push_back(i - males);
  239.             }
  240.         }
  241.         cout << sz(m_inv) + sz(f_inv) << "\n";
  242.         cout << sz(m_inv) << " " << sz(f_inv) << "\n";
  243.         cout << m_inv << "\n" << f_inv << endl;
  244.     }
  245. };
  246.  
  247. int main() {
  248. //    ios::sync_with_stdio(false);
  249. //    std::cin.tie(0);
  250. //    freopen("in", "r", stdin);
  251. //    freopen("out", "w", stdout);
  252.     int k; cin >> k;
  253.     while (k--) {
  254.         auto s = solver<int>();
  255.         s.output_biclique();
  256.         cout << "\n";
  257.     }
  258.     return 0;
  259. }
Advertisement
Add Comment
Please, Sign In to add comment