ABBC

아직 간선의 방향이 정해지지 않은, 무향 그래프가 주어진다.

다음 조건을 모두 만족하는 세 정점쌍 의 개수를 ABBC라고 하자.

• 조건 1) 세 정점 , , 는 서로 달라야 한다.
• 조건 2) 정점 에서 정점 로 가는 간선이 존재한다.
• 조건 3) 정점 에서 정점 로 가는 간선이 존재한다.

당신의 목표는, ABBC의 값을 최대화하는 것이다.

이를 위하여 당신은 모든 간선의 방향을 결정해야 한다. 간선을 클릭하면 간선의 방향을 설정할 수 있다.

당신은 총 다섯 개의 부분 문제를 해결해야 한다. 부분 문제는 상단의 "문제 " 버튼을 눌러서 선택할 수 있다.

채점 방식

다섯 문제를 모두 해결하지 않아도 부분 점수를 받을 수 있다.

각 문제에서 목표를 달성하면, 각각 전체 점수의 20%를 받는다.

목표를 달성했다면 반드시 제출을 해야 득점할 수 있다.

문제 형식

인터랙티브

출처

• KOI 2023 1차대회 고등부 1교시 19번
• KOI 2023 1차대회 중등부 1교시 20번