BOJ 17193 - I Would Walk 500 Miles

BOJ 17193 - I Would Walk 500 Miles

$O(V^2)$ 프림 알고리즘을 구성한다음 작은것부터 $N-K$ 개를 없애준 다음 나오는 간선의 가중치가 정답이다.

왜냐면 $K$ 개의 그룹으로 만들어준 다는 것은 MST에서 $N-K$ 개의 간선들을 제거하고 그 그룹을 합쳐서 최소값을 삭제해줄 수 있다는 뜻이다.

MST가 구성되었을 때 $N-1$ 개의 간선이 항상 모든 간선들 중 최소로 뽑힌 것이기 때문에 거기서 지워야한다.

const int inf = 2e18;
void solve() {
   int n, k;
   auto d = [&](int i, int j) {
      return md(2019201997, i * 2019201913 + 2019201949 * j);
   };
   cin >> n >> k;
   vi used(n + 1), shortest(n + 1, inf);
   used[1] = 1;
   for (int i = 2; i <= n; i++) shortest[i] = d(1, i);
   vi costs;
   for (int i = 2; i <= n; i++) {

      int nxt = -1;
      for (int j = 1; j <= n; j++) {
         if (!used[j] && (nxt == -1 || shortest[nxt] > shortest[j])) {
            nxt = j;
         }
      }
      costs.pb(shortest[nxt]);
      used[nxt] = 1;

      for (int j = 1; j <= n; j++) {
         if (!used[j]) {
            mina(shortest[j], d(j, nxt));
         }
      }
   }
   sort(all(costs));
   cout << costs[n - k];
}