https://www.acmicpc.net/problem/24889
문제요약
- 노드 N, 간선 N 그래프가 주어짐. 모두 연결(N 20만)
- s, e, w : s->e까지 간선/노드를 한번씩만 이용해서 이동. 차량이 이동할 가능성이 있는 간선은 모두 w 통행량이라고 계산
- 이런 집단이 M개 주어짐(20만)
- 1 ~ N번 간선에 대해 통행량 구하기
접근법
- O(NM) : M개의 집단에 대해 각각 처리. BFS를 하든 DFS를 하든. 여러가지 조건을 고려해서 처리해야할 듯
- cycle
- 모두 이어져있고, 간선이 N개이므로 반드시 cycle이 생김.
- 그냥 트리면 s-e의 방법이 한개만 될 것임
- cycle이 있는 경우에 간단하게 생각해보면
- cycle을 지나가면 : cycle 내의 간선은 모두 이용하게 됨
- cycle을 안 지나가면 : 그냥 보통의 간선처럼 이용하게 됨
- cycle도 판단해야겠지만, cycle의 외부이면 cycle까지 오는 간선은 무엇이며 언제 끝나고, 처리는 어떻게 하고....
- cycle의 경우에도 둘다 cycle에 있는지, 하나만 바깥인지, 둘다 바깥인데 cycle을 통과하는지, 통과하더라도 한점만 통과하는지...
- cycle 집단을 한개의 노드로 표현하고 그래프로 재구성 하기
- 괜찮아 보임
- 두 점 모두 cycle이면 cycle 간선에 대한 적절한 처리(나중에 합해서 출력)
- lca를 활용해서 두 점이 어디를 통과하는지 판단 가능
- cycle 바깥이면 => 일반 간선처럼 처리
- 한쪽이 cycle에 있으면 => 바깥쪽은 일반 간선, cycle 처리
=> 이때 간과한 점이 있었음. cycle을 지나더라도 한 점만 사용하면 cycle을 모두 통과하지 않게됨. 일일이 따지자니
- 통행량 처리
- ETT, HDL... 등이 생각났으나 힘듬
- 차량이 이동할때 시작->부모->더 부모->...->공통조상->다른쪽자식->더 자식->...->끝 이런 식으로 이동할 것임
- +1, -1 기법처럼 시작에 +를 시켜주고 끝지점에 -를 시켜준 후 나중에 아래에서부터 누적해서 더하면 될 것 같음
- cycle은 별도 처리하는데, cycle을 이용한 횟수를 별도로 구해서 나중에 계산해줌
- cycle의 처리(다시)
- 간과한점도 생기고 골치아픈 것도 생겨서 이를 처리해야함
- cycle의 한 간선만 끊고, 임의의 점을 루트로 해서 그래프를 구성하자니 빠지는 조건들이 많음
- 각 점들이 cycle의 각 점과 만나고, cycle의 각 점을 루트로 하는 여러개의 트리를 만들면 뭔가 될 것 같은데 트리가 엄청 많아지고 관리도 안될 것 같음
- cycle의 각 점이 임의의 한 점을 바라보게 해서 트리를 만들고, cycle끼리의 간선은 끊어냄
- cycle 바깥에서 만나는 점들 => 상관 없음
- 두 점 모두 cycle => 상관없음
- cycle에서 만나는데 서로 다른 cycle 점을 이용하는 경우 => lca가 새로 생성한 점이 될 것임
- cycled에서 만나는데 같은 cycle 점을 이용하는 경우(cycle 사용은 안하는 경우) => lca가 cycle 내의 한 점이 될 것임
- 간선의 처리
- 트리 구성시 부모로부터 이어진 간선이 있을텐데, 그 점을 해당 노드의 간선으로 정하고 처리함
공식해설
- 공식해설을 보니 각각의 트리로 처리해서 같은 트리인지, 다른 트리인지 판단하는 것도 괜찮아 보임
newbieski