Advertisement
Guest User

Untitled

a guest
Dec 14th, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.00 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <list>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. bool kuhn(int v, vector<bool> &used, vector<int> &match, list<list<int>> G) {
  10. if (used[v]) return false;
  11. used[v] = true;
  12. list<list<int>>::iterator iter = G.begin();
  13. for (int i = 0; i < v; i++)
  14. iter++;
  15. list<int>::iterator u;
  16. for ( u = (*iter).begin();u != (*iter).end(); u++) {
  17. if (match[*u] == -1 || kuhn(match[*u], used,match,G)) {
  18. match[*u] = v;
  19. return true;
  20. }
  21. }
  22. return false;
  23. }
  24.  
  25. int main() {
  26.  
  27. ifstream in;
  28. in.open("matching.in");
  29. ofstream out;
  30. out.open("matching.out");
  31. int n;
  32. in >> n;
  33.  
  34. vector<bool> used(n);
  35. vector<int> match(n,-1);
  36. list<list<int>> G(n);
  37.  
  38. vector<pair<int,int>> vertex(n);
  39. for (int i = 0; i < n; i++) {
  40. int elem;
  41. in >> elem;
  42. vertex[i] = {i,elem};
  43. }
  44.  
  45. std::sort(vertex.begin(), vertex.end(), [](std::pair<int,int> &left,
  46. std::pair<int,int> &right) {
  47. return left.second < right.second;
  48. });
  49.  
  50. int cap;
  51. list<list<int>>::iterator iter;
  52. for ( iter = G.begin(); iter != G.end(); iter++){
  53. in >> cap;
  54. list<int>::iterator j;
  55. int k = 0;
  56. for (j = (*iter).begin(); k < cap; j++) {
  57. k++;
  58. int elem;
  59. in >> elem;
  60. (*j) = elem;
  61. cout << *j << " ";
  62. }
  63. cout << endl;
  64. }
  65.  
  66. for(int i = 0; i < n; i++){
  67. //used.resize(n,false);
  68. for(int j = 0; j < used.size() ; j++) {
  69. used[j] = false;
  70. }
  71. kuhn(vertex[i].first,used,match,G);
  72. }
  73.  
  74. vector<int> answer(n + 1);
  75. for (int i = 0; i < n; i++) {
  76. if(match[i] != -1){
  77. answer[match[i] + 1] = i + 1;
  78. }
  79. }
  80.  
  81. for (int i = 1; i <= n ; i++) {
  82. cout << answer[i] << " ";
  83. }
  84.  
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement