BOJ 24977 - Visits

BOJ 24977 - Visits

이 문제는 어렵지 않다.

결국 permutation graph이기 때문에 $\rho$의 모양의 그래프가 생기고 거기서 싸이클에서 가장 작은 $v_i$ 를 가진 것 하나만 지워주면 가능하다.

그런데 이건 그냥 MST와 동치라서 MST로 구해줄 수 있다.

풀 땐 토끼와 거북이 알고리즘까지 썼다.

void solve() {
   int n;
   cin >> n;
   vector<pi> a(n);
   vvi edges(n);
   int ans = 0;
   for (auto &[a, v]: a) cin >> a >> v, a--, ans += v;
   for (int i = 0; i < n; i++) edges[i].pb(a[i].fi), edges[a[i].fi].pb(i);
   vi vis(n);
   for (int i = 0; i < n; i++) {
      if (vis[i]) continue;
      int x = i, y = i;

      do {
         x = a[x].fi;
         y = a[a[y].fi].fi;
      } while (x ^ y);
      x = i;
      while (x ^ y) {
         x = a[x].fi;
         y = a[y].fi;
      }
      vi cycle;
      int start = x;
      int mn_cost = 2e15;
      do {
         cycle.pb(x);
         mina(mn_cost, a[x].se);
         x = a[x].fi;
      } while (x != start);
      ans -= mn_cost;
      queue<int> q;
      q.push(x);
      vis[x] = 1;
      while (sz(q)) {
         int cur = q.front();
         q.pop();
         for (int to: edges[cur]) if (!vis[to]) vis[to] = 1, q.push(to);
      }
   }
   cout << ans;
}