시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 130 | 26 | 21 | 31.343% |
항승이네 마을에서 결혼이란 일반적인 결혼과는 약간 다르다. 항승이네 마을에서 결혼이란 한 명의 남편과 여러 명의 부인, 또는 여러 명의 남편과 한 명의 부인을 의미한다.
항승이네 마을에 남자가 총 N명, 여자가 총 M명 있다. 어떤 남자와 어떤 여자가 결혼을 하려면, 서로가 서로에게 호감이 있어야 한다.
항승이가 마을의 촌장으로써 할 일은 남자와 여자를 결혼을 시키는 것인데, 가능한 결혼의 개수를 최소화시키는 것이다. 모든 사람은 반드시 하나의 결혼을 해야만 한다. 즉, 결혼을 하지 않는 경우는 없다. 그 때 가능한 결혼의 수의 최솟값을 구하는 프로그램을 작성하시오. 모든 사람이 결혼을 할 수 없는 경우에는 -1을 출력한다.
첫째 줄에 N과 M이 주어진다. N과 M은 12보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에는 i번 남자와 1,2,3,...M번 여자가 호감이 있으면 1 없으면 0이 주어진다.
첫째 줄에 결혼의 개수의 최솟값을 출력한다. 만약 모든 사람이 결혼을 할 수 없으면 -1을 출력한다.
4 4 0001 0001 0001 1111
2
1 3 111
1
2 2 00 00
-1
3 3 100 010 001
3