20. ABBC(15점)
작성자
kangcoding
작성일
2024-05-23 01:52
조회
405
아직 간선의 방향이 정해지지 않은, 무향 그래프가 주어진다.
다음 조건을 모두 만족하는 세 정점쌍 (a, b, c)의 개수를 ABBC라고 하자.
- 조건 1) 세 정점 a, b, c는 서로 달라야 한다.
- 조건 2) 정점 a에서 정점 b로 가는 간선이 존재한다.
- 조건 3) 정점 b에서 정점 c로 가는 간선이 존재한다.
당신의 목표는, ABBC의 값을 최대화하는 것이다.
이를 위하여 당신은 모든 간선의 방향을 결정해야 한다. 간선을 클릭하면 간선의 방향을 설정할 수 있다.
당신은 총 다섯 개의 부분 문제를 해결해야 한다. 부분 문제는 상단의 “문제 x” 버튼을 눌러서 선택할 수
있다.
채점 방식
다섯 문제를 모두 해결하지 않아도 부분 점수를 받을 수 있다.
각 문제에서 목표를 달성하면, 각각 전체 점수의 20%를 받는다.
목표를 달성했다면 반드시 제출을 해야 득점할 수 있다.
========== 풀이 ==========
3개의 노드가 2개의 간선으로 연결되는 개수를 최대한 많이 만들면 된다.
이때 방향이 존재 하므로 방향만 조금 주의해서 만들면 된다.
밑에 주어진 방향과 반대로 해도 가능하다.
전체 0