일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- spfa
- 세그먼트트리
- 트라이
- 디닉
- 이분탐색
- Segment tree
- LCA
- 트리dp
- 전월세
- lcp
- 유량
- 투룸
- MCMF
- 2SAT
- 2-sat
- Seg
- 좌표압축
- 아호코라식
- 오블완
- 접미사배열
- 티스토리챌린지
- 월세
- dinic
- suffix array
- 이분매칭
- 구현
- SCC
- 임대차계약
- treedp
- TRIE
Archives
- Today
- Total
목록트리dp (1)
N coding
15940_네트워크 연결
ucpc c번 구현이 극혐이긴한데 또 생각보다 별거 없기도 하다. 내가 https://www.acmicpc.net/problem/13016 문제를 푼거랑 비슷한 방식의 트리dp를 사용하면 된다. ucpc 당시에는 원래 그래프에서 트리의 지름을 하나 구하고 트리의 지름에 속하지 않는 노드를 가지고 다시 sub지름을 구해서 잘 연결해준다. 로 접근했었는데 이러면 트리에 같은 크기를 갖는 지름이 여러개 있을 경우 어떤 지름을 원래 지름으로 선택하느냐에 따라서 최대값이 이상하게 나올 수 있다. 그래서 정해는 모든 간선을 잘라본다. 이다. 근데 모든 간선을 자를때마다 subtree의 지름과 그 subtree를 제외한 나머지 트리의 지름을 구해서 연결하면 O(n^2)이 된다. 본선당시에 다들 n^2까진 생각했을 것..
PS
2018. 8. 29. 22:05