gen-bipartite-graph.cpp 1.4 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
  1. #include "testlib.h"
  2. #include <iostream>
  3. #include <sstream>
  4. #include <fstream>
  5. #include <iomanip>
  6. #include <string>
  7. #include <cstdlib>
  8. #include <cstdio>
  9. #include <cstring>
  10. #include <cmath>
  11. #include <ctime>
  12. #include <climits>
  13. #include <cassert>
  14. #include <vector>
  15. #include <queue>
  16. #include <stack>
  17. #include <deque>
  18. #include <set>
  19. #include <map>
  20. #include <bitset>
  21. #include <utility>
  22. #include <algorithm>
  23. #define forn(i, n) for (int i = 0; i < int(n); i++)
  24. using namespace std;
  25. int main(int argc, char* argv[])
  26. {
  27. registerGen(argc, argv, 1);
  28. int n = atoi(argv[1]);
  29. int m = atoi(argv[2]);
  30. size_t k = atoi(argv[3]);
  31. int t = rnd.next(-2, 2);
  32. set<pair<int,int> > edges;
  33. while (edges.size() < k)
  34. {
  35. int a = rnd.wnext(n, t);
  36. int b = rnd.wnext(m, t);
  37. edges.insert(make_pair(a, b));
  38. }
  39. vector<pair<int,int> > e(edges.begin(), edges.end());
  40. shuffle(e.begin(), e.end());
  41. vector<int> pa(n);
  42. for (int i = 0; i < n; i++)
  43. pa[i] = i + 1;
  44. shuffle(pa.begin(), pa.end());
  45. vector<int> pb(m);
  46. for (int i = 0; i < m; i++)
  47. pb[i] = i + 1;
  48. shuffle(pb.begin(), pb.end());
  49. cout << n << " " << m << " " << e.size() << endl;
  50. forn(i, e.size())
  51. cout << pa[e[i].first] << " " << pb[e[i].second] << endl;
  52. return 0;
  53. }