시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 263 82 66 33.166%

문제

1부터 n까지의 번호가 매겨진 n개의 점과 m개의 간선들로 이루어진 연결그래프가 주어진다. 두 점을 직접 잇는 간선은 최대 1개이며, 자기 자신을 잇는 루프는 없다.

여기서 이 그래프의 각 간선을 저항이 1Ω인 도선들로 생각하면 이 그래프를 전기회로로 생각할 수 있다.

이 전기회로에 대하여, 간선으로 직접 이어진 모든 쌍의 점 A, B 에 대해, AB 사이의 합성저항 값의 총합을 Ω 단위로 구하시오. 즉, m개 쌍의 점 사이의 합성저항의 총합을 구하면 된다.

입력

첫 줄에 점의 개수 과 간선의 개수 이 주어진다. (m  n 은 1000을 넘지 않는다.)

두 번째 줄부터 n+1 번째 줄까지는 간선으로 이어진 두 점의 번호가 주어진다.

출력

간선으로 직접 이어진 모든 쌍의 점 A, B 에 대해 합성저항 값의 합을 소수점 넷째자리에서 반올림한 값을 출력한다.

예제 입력 1

4 4
1 2
2 3
3 1
1 4

예제 출력 1

3.000

점 1과 2 사이의 합성저항은 2/3Ω이고, 2와 3은 2/3Ω, 3과 1도 2/3Ω, 1과 4는 1Ω이다. 따라서 이들의 총합은 3Ω이다.

출처

Contest > 구데기컵 > 진짜 구데기컵 2018 ⚡번

  • 문제를 만든 사람: veydpz