목록Floyd (2)
블로그 옮겼습니다
Codeforces Round #119 (Div. 1) B. AlgoRace
그래프 + dp 이다. N
Algorithm/Problem Solving
2017. 3. 26. 01:10
BOJ 11097번 도시 계획
1c, a->c 가 연결 되어있다면 a->c 가 없어도 a에서 b를 통해 c로 갈 수 있기 때문에 a->c 는 필요 없는 간선이 된다. 아무튼 이런 쓸모없는 간선들을 찾아서 지워주는게 문제의 핵심인데, 문제는 어떻게 해야하느냐이다. 우선 확실한건 같은 SCC내에 있는 노드 K개가 있다면 이 들이 SCC를 이루기 위한 최소한의 간선 수는 K개 이다. 이 것은 자명하다. 그리고 다른 SCC간의 간선은 딱 하나만 필요하므로 정점 압축을 한뒤 플로이드로 불필요한 간선을 지울 수가 있다. u -> k 이고 k -> v이면 u -> v 는 필요없다는 식으로 지울수있다. 그리고 SCC를 묶지않고 처음부터 플로이드로만 불필요한 간선을 지우면 되지않을까해서 새로 짜봤는데 틀렸는데, 생각을 좀 해보면. 같은 SCC 내에 ..
Algorithm/Problem Solving
2017. 3. 19. 12:22