구사과

https://www.acmicpc.net/problem/2430쉽게 가자. 만약에 두 트리의 루트 T1, T2가 주어졌다면 어떨까?* 1. T1과 T2에서 BFS를 돌린다.* 2. 그래프에 모든 에지들을 T1쪽에 속하는지, T2쪽에 속하는지 분류하는 방법을 알려주자면, i - j를 잇는 에지에 대해서 (D(T1, i) + D(T1, j)) / 2와 ((D(T2, i) + D(T2, j)) / 2를 생각해보자. (무게 중심) 두 값중 작은 쪽이 존재한다면, 그 쪽에 속하는 에지로 보내버리고, 만약에 두 값이 같다면 이건 거울대칭트리 그래프가 아니다. 이렇게 하면 두개의 트리가 만들어 진다. 트리가 아닌 다른 게 만들어졌다면 (E != V-1) NO 찍자. * 3. 리프 번호가 같고, 트리의 구성 에지가 ..

소수 없는 수열 (BOJ 4241)https://www.acmicpc.net/problem/4241백트래킹 노잼 ㅠㅠ One way roads (BOJ 7724. CPSPC 2010)https://www.acmicpc.net/problem/7724그래프가 트리인 경우를 생각해 보자. 주어지는 쿼리들은 트리에 있는 정해진 간선들의 방향을 고정시킨다. 이것은 O(N)에 시뮬레이션할 수도 있지만, LCA를 구한 후, 변홧값만 칠해주면 O(lgN)에도 가능하다. (USACO Dec15 Maxflow 참고. http://usaco.org/index.php?page=viewproblem2&cpid=576) 모든 변홧값이 칠해지면, 두 방향 모두를 가르켜야 하는 에지가 존재할 경우 불가능. 한 방향만 가르키면 된다면..

http://oj.uz/problems/view/balkan11_timeismoney처음에 이러한 문제를 딱 보고 생각이 난건, 한쪽의 sum을 고정시키고 진행하는 knapsack 류의 방법인데 (다익스트라가 그렇게 되니까) 해보면 알겠지만 Prim / Kruskal에서 그런 짓을 하는 거랑 다익스트라에서 하는 거랑은 느낌이 많이 다르다 (ㅜㅜ). 정점 V, 간선 E, max(t, c) = M = 255라고 하겠다. O(ElgE * (VM)^2) / O(V^4M^2) 중요한 고찰이 필요하다. 나올 수 있는 모든 MST의 경우의 수를 (Sigma(T), Sigma(C)) 좌표 형태로 좌표평면에 찍었을 때, xy를 최소화하는 점을 골라야 한다. 최소인 점을 찾았다 치고, 그 점에서 y = T/x의 도함수 값..