네트워크 파괴자

시간 제한1초메모리 제한128 MB

요약

N개의 노드(N <= 20)를 두 집합 A와 B로 나눌 때 두 집합 사이를 지나는 간선 가중치 합이 최대가 되도록 한다.

난이도: 보통10점 중 5점
유형: 완전 탐색, 백트래킹, 구현
정답자: 아직 제출이 없습니다

문제

어느 대학교의 네트워크는 $N$ 대의 컴퓨터로 이루어져 있다. 시스템 관리자들은 모든 노드 쌍 사이의 트래픽을 측정한 뒤, 두 부분 사이를 오가는 트래픽이 최소가 되도록 네트워크를 두 개의 하위 네트워크로 나누어 두었다.

대학교에서 퇴학당한 것에 앙심을 품은 학생 Vasya는 정반대의 일을 하려 한다. 그는 네트워크를 장악한 뒤, 두 하위 네트워크 사이의 트래픽이 최대가 되도록 컴퓨터들을 다시 배치하고 싶어 한다. 이 최악의 분할을 계산하는 문제를 스스로 풀 수 없어서, 그는 당신에게 도움을 청한다.

트래픽은 행렬 $C$ 로 주어지며, $C_{ij}$ 는 노드 $i$ 와 노드 $j$ 사이에 오가는 데이터의 양이다. 이 행렬은 대칭이고( $C_{ij} = C_{ji}$ ) 자기 자신과의 트래픽은 없다( $C_{ii} = 0$ ). $N$ 개의 노드를 서로소인 두 집합 $A$ 와 $B$ 로 나누어 다음 값을 최대로 만들어라.

$\sum_{i \in A,\; j \in B} C_{ij}.$

입력

첫째 줄에 노드의 개수 $N$ 이 주어진다 ( $2 \le N \le 20$ ).

이어지는 $N$ 개의 줄에는 각각 $N$ 개의 정수가 공백으로 구분되어 주어진다. $i$ 번째 줄의 $j$ 번째 정수는 $C_{ij}$ 이다 ( $0 \le C_{ij} \le 10000$ ). 행렬은 대칭이며 대각 성분은 $0$ 이다.

출력

두 하위 네트워크 사이를 오가는 트래픽의 최댓값을 정수 하나로 출력한다.

예제4

예제 1
입력
```
3
0 50 30
50 0 40
30 40 0
```
예상 출력
```
90
```
예제 2
입력
```
2
0 100
100 0
```
예상 출력
```
100
```
예제 3
입력
```
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
```
예상 출력
```
4
```

예제 4

입력

예상 출력