[BOJ] 11745: King’s Inspection
11745: King’s Inspection 풀이 M <= N+20이므로, 주어지는 그래프는 최대 20개의 간선만 제거하면 트리가 된다. 즉, 트리와 아주 유사하게 생겼다는 뜻이고, 이는 대부분 노드의 in/out degree가 1이라는 뜻이다. indegree 또는 outdegree가 2 이상인 노드를 special node로 두자. special node에서 다른 speical node까지의 경로를 압축하자. in/out degree가 1인 노드들을 모두 압축해서 하나의 간선으로 치는 것이다. 그러면 노드가 많아야 40개인 그래프가 나온다. 이 그래프에서 TSP를 하면 된다. 코드 #include <bits/stdc++.h> using namespace std; typedef long long ll;...