크레이지함

큰 모임(명절 등)이 끝난 뒤 가족에 대해 물어보면, 사람들은 대개 자기 가족이 얼마나 크레이지한지 이야기한다.1 몇 년 동안 서로를 알아 온 데다 아마 유전적으로도 비슷하기 때문에, 가족 구성원들은 서로를 어떻게 자극하고 짜증 나게 할지 정확히 안다. 평소 조용한 사람들도 같은 방에 모이면 갑자기 미친 듯이 거칠어진다. 여기서는 총 크레이지함이 최대가 되도록 어떤 가족을 초대할지 계산하려 한다.

가족 구성원 i, j의 각 쌍마다 (양수 또는 음수) 수 $c_{i,j}$가 주어진다. 이는 둘 다 초대되었을 때 이 쌍이 기여하는 크레이지함이다. 음수는 이 쌍이 오히려 분위기를 가라앉힌다는 뜻이다. 목표는 비어 있지 않은(즉, 적어도 한 명은 초대해야 하는) 부분집합을 찾아 총 크레이지함이 최대가 되도록 하는 것이다. 총 크레이지함은 초대된 가족 구성원의 모든 쌍에 대한 크레이지함의 합에 모든 손님의 개별 크레이지함을 더한 값이다.

1연어에게 왜 몇 주씩 강을 거슬러 헤엄치냐고 물으면 아마 이렇게 말할 것이다. "그 파티를 빠질 수 없어. 우리 연어 가족은 크레이지하다고!!!"

첫 줄에는 파일에 들어 있는 입력 데이터 세트의 수 $K \ge 1$이 주어진다. 그다음에 다음 형식의 데이터 세트 $K$개가 이어진다.

데이터 세트의 첫 줄에는 선택할 친척의 수 $2 \le n \le 20$이 주어진다. 이어서 $n$개의 줄이 주어지며, 각 줄에는 $n$개의 실수 $-1000.0 \le c_{i,j} \le 1000.0$이 있다. $c_{i,j}$는 i와 j를 둘 다 초대했을 때 더해지는 크레이지함이다. 모든 i와 j에 대해 $c_{i,j} = c_{j,i}$임이 보장된다. $c_{i,i}$는 구성원 i 본인이 기여하는 크레이지함이다.

각 데이터 세트마다 먼저 "Data Set x:"를 한 줄에 출력한다. 여기서 x는 데이터 세트의 번호이다. 그다음 이 친척들의 비어 있지 않은 부분집합을 초대해 얻을 수 있는 최대 총 크레이지함을 소수점 둘째 자리로 반올림해 출력한다.