Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include<iostream>
- #include<algorithm>
- #include<stdio.h>
- #include<algorithm>
- #include<math.h>
- #include<vector>
- #include<set>
- #include<map>
- using namespace std;
- const int maxn = 505;
- int n, m;
- bool matrix[maxn][maxn];
- bool mark[maxn];
- int lm[maxn];
- int rm[maxn];
- bool dfs(int v) {
- mark[v] = true;
- for (int i = 1; i <= m; i++) {
- if (!matrix[v][i])
- continue;
- if (rm[i] == -1 || (!mark[rm[i]] && dfs(rm[i]))) {
- rm[i] = v;
- lm[v] = i;
- return true;
- }
- }
- return false;
- }
- void win() {
- printf("Y\n");
- for (int i = 1; i < n; i++)
- printf("%d ", lm[i]);
- printf("%d", lm[n]);
- }
- void fail(int xi) {
- printf("N\n%d", xi);
- }
- void solve() {
- scanf("%d%d", &n, &m);
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= m; j++) {
- int cur;
- scanf("%d", &cur);
- matrix[i][j] = cur;
- }
- fill(mark, mark + maxn, false);
- fill(lm, lm + maxn, -1);
- fill(rm, rm + maxn, -1);
- for (int i = 1; i <= n; i++) {
- if (!mark[i]) {
- fill(mark, mark + maxn, false);
- dfs(i);
- }
- }
- for (int i = 1; i <= n; i++) {
- if (lm[i] == -1)
- return fail(i);
- }
- return win();
- }
- int main() {
- freopen("in.txt", "rt", stdin);
- freopen("out.txt", "wt", stdout);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement