시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (하단 참고) | 512 MB | 37 | 14 | 12 | 42.857% |
Bob은 이분 그래프 (Bipartite Graph)를 이용한 놀이를 즐겨한다. 이 문제에서는 아래와 같이 임의의 이분 그래프 $H = (X + Y, E)$를 정의한다:
Bob은 아래 규칙에 따라 이분 그래프 놀이를 한다:
예를 들어 X = {x1, x2}, Y = {y1, y2}, E = {(x1, y1), (x2, y1), (x2, y2)}라 하자 (아래 그림 참고).
이 때 위 규칙에 따라 노드들에 가중치를 부여하는 방법은 총 2! × 2! = 4가지 존재한다.
H의 "최대 점수"는 위와 같이 가능한 모든 가중치를 부여하는 방법 중 H의 점수를 최대화 했을 때 얻을 수 있는 점수로 정의하자 -- 편의상 이를 S(H)라 하자. Bob은 임의의 이분 그래프 H의 "최대 점수"를 구하는 놀이를 즐겨하지만 이제 너무 잘하게 되어 지루해하던 참이다.
마침 이를 지켜보던 Alice는 새로운 놀이를 제안했다. 그래프 H의 간선 중 임의로 i번째 간선을 지워 새로운 이분 그래프를 얻을 수 있는데, 이를 Hi라 하자 (아래 그림 참고).
S(Hi)는 그래프 Hi의 "최대 점수"이며 상기한 정의에 따라 구할 수 있다. 예를 들어 위의 예제에서 H1은 원래 그래프 H에서 (x1, y1)을 삭제한 그래프이며, 이 때 S(H1)은 7이다 (이를 달성하려면 v1 = 1, v2 = 2 이어야 한다). 같은 예제에서 H2은 (x2, y1)을 삭제한 그래프이며, 이 때 (v1, v2, w1, w2) 값에 관계없이 S(H2)는 6이다. S(H3)은 7이며, 따라서 이 경우 S(H1), S(H2), S(H3) 의 최댓값은 7이다.
Alice의 제안대로 Bob은 S(H)뿐 아니라 S(H1), S(H2), ..., S(Hk)의 최댓값을 구해보려고 한다. Bob을 도와주자.
입력 첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 줄에는 n, m, k가 공백으로 구분되어 주어진다. 다음 k개의 줄에는 각 줄에 간선을 나타내는 2개의 정수가 공백으로 구분되어 주어지며 X의 노드 인덱스와 Y의 노드 인덱스를 나타낸다 (즉, xi와 yj를 잇는 간선은 "i j"로 주어진다).
각 테스트 케이스의 정답인 두 개의 정수를 각 줄에 출력한다. 첫 번째 정수는 S(H)이며 두 번째 정수는 S(H1), ..., S(Hk)의 최댓값이다.
3 1 5 2 1 5 1 4 2 2 3 1 1 2 1 2 2 3 2 4 1 1 2 1 2 2 3 2
11 6 10 7 15 13
예제 1: 한 가지 방법으로 v1 = 1, w4 = 4, w5 = 5인 경우 S(H) = 11이 된다. S(H1) = S(H2) = 6이다.
예제 2: 본문에서 다루었다.
예제 3: 설명 없음.