Advertisement
Guest User

Untitled

a guest
Dec 19th, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.27 KB | None | 0 0
  1. #include <fstream>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6. ifstream in("in.txt");
  7. ofstream out("out.txt");
  8. int k, l;
  9. in >> k >> l;
  10. int *g = new int [k * l];
  11. for (int i = 0; i < k; ++i) {
  12. for (int j = 0; j < l; ++j) {
  13. in >> g[i * l + j];
  14. }
  15. }
  16. int *matchX = new int[k];
  17. int *matchY = new int[l];
  18. bool *visited = new bool[l];
  19. for (int i = 0; i < k; ++i) {
  20. matchX[i] = -1;
  21. }
  22. for (int j = 0; j < l; ++j) {
  23. matchY[j] = -1;
  24. }
  25. for (int i = 0; i < k; ++i) {
  26. int current = i;
  27. for (int s = 0; s < l; ++s) {
  28. visited[s] = false;
  29. }
  30. while (true) {
  31. int v = -1;
  32. for (int p = 0; p < l; ++p) {
  33. if (!visited[p] && g[current * l + p] == 1) {
  34. v = p;
  35. break;
  36. }
  37. }
  38. if (v == -1) {
  39. out << "N\n";
  40. out << i + 1;
  41. return 0;
  42. }
  43. if (matchY[v] == -1) {
  44. matchX[current] = v;
  45. matchY[v] = current;
  46. break;
  47. }
  48. else {
  49. int next = matchY[v];
  50. matchX[current] = v;
  51. matchY[v] = current;
  52. current = next;
  53. visited[v] = true;
  54. }
  55. }
  56. }
  57. for (int j = 0; j < l; ++j) {
  58. if (matchY[j] == -1) {
  59. out << "N\n";
  60. out << k;
  61. return 0;
  62. }
  63. }
  64. out << "Y\n";
  65. for (int i = 0; i < k; ++i) {
  66. out << matchX[i] + 1 << " ";
  67. }
  68. in.close();
  69. out.close();
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement