Informatica Online Judge

  최소 경로 커버 [2359 / 0937]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 1   Total Tried : 2


The Champion of this Problem (C++) : gs18089 - ms / 2432byte
My Best Submission (C++) : N/A

[36th 이종영 (gs18089)]
Writer ID : [gs18089]

Background

N개의 정점과 정점들을 잇는 단방향 간선들이 있다. N개의 정점 중 몇개의 정점은 흰색 정점이고, 나머지 정점은 검은색 정점이다. 이 그래프의 정점을 색칠하기 위해, 그래프 상에서 하나의 경로를 골라 경로 상의 모든 정점들을 검은색 정점으로 만들 수 있다. 그래프 상의 모든 정점을 검은색 정점으로 만들기 위한 경로의 최소 개수는 무엇일까?

Input

첫 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄에 N개의 수가 주어진다. i번째 수가 1이면 i가 흰색 정점이란 뜻이며, 0이면 검은색 정점이란 뜻이다. 그 후 N개의 줄에 걸쳐 N개의 수가 주어진다. i번째 줄의 j번째 수가 1이면 i번 정점에서 j번 정점으로 가는 간선이 있다는 뜻이며, 0이면 없다는 뜻이다.

Output

모든 흰색 정점을 검은색으로 만들 때 최소로 필요한 경로의 개수를 출력한다.

IO Example

입력1
4
1 1 1 1
0 1 1 0
0 0 0 1
0 0 0 1
0 0 0 0

출력1
2

입력2
6
1 1 1 1 1 1
0 1 0 0 0 0
0 0 1 0 1 0
0 0 0 1 0 0
0 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

출력2
2

입력3
4
1 0 1 1
0 1 1 0
0 0 0 1
0 0 0 1
0 0 0 0

출력3
1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]