Advertisement
ProgrammerMaf

Untitled

Jan 19th, 2017
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<stdio.h>
  5. #include<algorithm>
  6. #include<math.h>
  7. #include<vector>
  8. #include<set>
  9. #include<map>
  10.  
  11. using namespace std;
  12.  
  13. const int maxn = 505;
  14.  
  15. int n, m;
  16.  
  17. bool matrix[maxn][maxn];
  18. bool mark[maxn];
  19. int lm[maxn];
  20. int rm[maxn];
  21.  
  22. bool dfs(int v) {
  23.     mark[v] = true;
  24.     for (int i = 1; i <= m; i++) {
  25.         if (!matrix[v][i])
  26.             continue;
  27.         if (rm[i] == -1 || (!mark[rm[i]] && dfs(rm[i]))) {
  28.             rm[i] = v;
  29.             lm[v] = i;
  30.             return true;
  31.         }
  32.     }
  33.     return false;
  34. }
  35.  
  36. void win() {
  37.     printf("Y\n");
  38.     for (int i = 1; i < n; i++)
  39.         printf("%d ", lm[i]);
  40.     printf("%d", lm[n]);
  41. }
  42.  
  43. void fail(int xi) {
  44.     printf("N\n%d", xi);
  45. }
  46.  
  47. void solve() {
  48.     scanf("%d%d", &n, &m);
  49.     for (int i = 1; i <= n; i++)
  50.         for (int j = 1; j <= m; j++) {
  51.             int cur;
  52.             scanf("%d", &cur);
  53.             matrix[i][j] = cur;
  54.         }
  55.     fill(mark, mark + maxn, false);
  56.     fill(lm, lm + maxn, -1);
  57.     fill(rm, rm + maxn, -1);
  58.     for (int i = 1; i <= n; i++) {
  59.         if (!mark[i]) {
  60.             fill(mark, mark + maxn, false);
  61.             dfs(i);
  62.         }
  63.     }
  64.     for (int i = 1; i <= n; i++) {
  65.         if (lm[i] == -1)
  66.             return fail(i);
  67.     }
  68.     return win();
  69. }
  70.  
  71. int main() {
  72.     freopen("in.txt", "rt", stdin);
  73.     freopen("out.txt", "wt", stdout);
  74.     solve();
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement