| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
- 18963
- 19911
- Journey to TST
- Atcoder
- 코드포스
- 미분방정식
- arc
- poi
- Kingdom Trip
- Hoof and Brain
- 알고리즘
- 일반해
- Joi
- Merlin QA
- 2018/2019
- 앳코더
- Классные парты
- BOJ
- Commuter Pass
- codeforces
- div1
- 24972
- Prok barrel
- 12126
- DP
- 15867
- 백준
- Subway
- C++
- JOISC
- Today
- Total
목록Subway (2)
취미로PS하는사람
저번에 이어서 Journey to TST set4를 풀려고 한다. https://psforhobby.tistory.com/60 [BOJ] Journey to TST set3 저번에 이어서 Journey to TST set3를 풀려고 한다. https://psforhobby.tistory.com/58 [BOJ] Journey to TST set2 저번에 이어서 Journey to TST set2를 풀려고 한다. https://psforhobby.tistory.com/57 [BOJ] Journey to TST set1 최근에 PS psforhobby.tistory.com https://dsstar.tistory.com/53 Journey to TST 문제 셋 공유 BOJ 그룹(https://www.acmic..
https://www.acmicpc.net/problem/8128 나의 접근 방식은 이러하다. 1. 리프 노드 사이로만 길을 놔야 한다. 이는 너무 당연하다. 2. 가장 점이 많이 포함되도록 길을 놓았을 때 그 점들의 집합은 끊어져 있지 않다. 만약 끊어져있다면 한 쪽의 한 경로와 다른 쪽의 한 경로의 한 끝점을 맞바꾸면 떨어진 두 컴포넌트 사이의 모든 정점도 포함되기 때문에 언제나 최적의 상태에서 위 조건을 만족하지 않을 수 없다는 것을 알 수 있다. 위 두 조건으로부터 최적 정점 집합은 리프 노드가 총 2*k개인 서브그래프라는 것을 알 수 있다. 이 때 포함된 정점 개수를 최대화 해야 한다. 3. 최적 점의 집합은 트리의 지름을 포함한다. 몇 번 그려보면 왠지 그럴 것 같다는 느낌을 받을 수 있다. ..