BOJ 22344 : 그래프 균형 맞추기
https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 개인적으로 이번 KOI 고등 1번 난이도>>>>>>>이번 KOI 고등 2번 난이도라고 생각한다. 먼저 모든 정점의 가중치를 x+a나 -x+b로 표현 가능하다. 이를 통해 가중치의 합의 최소 = 절댓값 함수에서의 최솟값을 이용하면 된다. 이때 사이클이 있을때의 예외를 잘 처리해야 하는데, 사이클이 있을 때 어떤 임의의 두 인접한 정점에서 유일한 x값이 나오는 경우가 있다. 이를 주의하..
2021.08.01