| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 225 | 76 | 56 | 32.184% |
어떤 무방향 가중치 그래프가 $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를 출력한다.
3 3 6 1 2 3 2 3 6 3 1 9
Yes
무슨 닫힌 보행을 선택하더라도 가중치의 합이 항상 $K$의 배수가 된다.
4 4 7 1 2 3 2 3 2 3 4 3 4 2 2
No
닫힌 보행으로 $ 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1 $을 선택하면 간선 가중치 합이 13ドル$이 되며, 이는 7ドル$의 배수가 아니다.
닫힌 보행이란 시작점과 끝점이 같으며, 같은 정점과 간선을 여러 번 방문할 수 있는 경로를 말한다.
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2023. 10. D번