BOJ 22344 : 그래프 균형 맞추기
2021. 8. 1. 01:08ㆍPS/Graph Theory
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값이 나오는 경우가 있다. 이를 주의하자.
'PS > Graph Theory' 카테고리의 다른 글
| BOJ 13361 : 최고인 대장장이 토르비욘 (0) | 2021.11.15 |
|---|---|
| BOJ 16562 : 친구비 (4) | 2021.02.25 |
| BOJ 10282 : 해킹 (0) | 2021.01.10 |
| BOJ 15663 : N과 M (9) (0) | 2020.06.02 |