월간 향유회 - $K$분 그래프

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	1024 MB	224	72	58	32.222%

문제

어떤 무방향 가중치 그래프가 $K$분 그래프라는 건, 그래프의 모든 닫힌 보행 $P$에 대해, $P$의 간선 가중치 합이 항상 $K$의 배수인 그래프를 의미한다. 이때 하나의 간선을 여러 번 사용했다면 간선 가중치 합에도 여러 번 더해진다.

무방향 가중치 그래프 $G$와 양의 정수 $K$가 주어질 때, $G$가 $K$분 그래프인지 판별해 보자.

첫째 줄에는 그래프 $G$의 정점 개수 $N$과 간선 개수 $M$, 그리고 문제에서 설명한 양의 정수 $K$가 공백으로 구분되어 주어진다. $(1\le N\le 300\, 000;$ $0\le M\le 500\, 000;$ $1\le K\le 10^9)$

이후 $M$개의 줄에 걸쳐 3개의 정수 $v_i,w_i,x_i$가 공백으로 구분되어 주어진다. 이는 $v_i$번 정점과 $w_i$번 정점을 연결하는 가중치 $x_i$의 양방향 간선을 의미한다. $(1\le v_i,w_i\le N;$ $0\le x_i\le 10^9)$

두 정점을 잇는 간선이 여러 개일 수 있으며, 같은 정점을 잇는 간선이 존재할 수 있다. 또한, 주어지는 그래프가 연결되어 있지 않을 수도 있다.

주어진 그래프가 $K$분 그래프라면 Yes를, 아니면 No를 출력한다.

Yes

무슨 닫힌 보행을 선택하더라도 가중치의 합이 항상 $K$의 배수가 된다.

No

닫힌 보행으로 $ 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1 $을 선택하면 간선 가중치 합이 $13$이 되며, 이는 $7$의 배수가 아니다.

닫힌 보행이란 시작점과 끝점이 같으며, 같은 정점과 간선을 여러 번 방문할 수 있는 경로를 말한다.

Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2023. 10. D번