BOJ 7577 - 탐사

image.png

System of Differential Constraints 의 대표적인 문제로, 부등식으로 나타내지는 조건들을 그래프로 구성해 벨만포드나 플로이드 와샬로 해를 구하는 문제이다.

a+w≥ba + w \ge b 에 대해서 a→ba \to b 로 가중치 ww의 간선을 이어주면 되고, 최대한 많은 constraints를 제약하면 된다.

sis_i를 ∑j=0iaj\sum_{j=0}^{i}a_j 라 할 때, si≤si+1≤si+1s_i \le s_{i+1} \le s_i+1 란 식에서 두 개의 부등식이 나오고

si−s0≤is_i - s_0 \le i 에서 한 개의 부등식이 나온다.

또한 li,ri,wil_i, r_i, w_i 에 대해 wi≤sri−sli−1≤wiw_i \le s_{r_i}-s_{l_i-1} \le w_i 로 또 두 개의 부등식이 나와서 이걸 모두 이어준다음 해를 찾아주면 된다.

음의 싸이클이 존재하면 정답은 불가능하다.

a+w≥ba + w \ge b 라는 부등식이 있어 간선을 이었는데 aa 까지의 최단경로가 계속해서 줄어들 수 있다면 언젠가 a+w<ba+w < b 가 되기 때문이다.

이 문제는 s0∼sks_0 \sim s_k 까지 총 k+1k+1 개의 정점을 만들고 s0s_0 에서 시작점으로 벨만 포드를 돌려서 해결할 수 있다.

void solve() {
   int k, n;
   cin >> k >> n;

   assert(k <= 40);

   vector<vector<pi>> edges(k + 1);
   for (int i = 1; i <= k; i++) edges[0].pb({i, i});

   for (int i = 1; i <= k; i++) {
      // s[i-1] <= s[i] <= s[i-1] + 1

      edges[i - 1].pb({i, 1});
      edges[i].pb({i - 1, 0});
   }

   for (int i = 0; i < n; i++) {
      int l, r, w;
      cin >> l >> r >> w;
      // w <= s[r] - s[l-1] <= w

      // 1. s[l-1] <= s[r] - w

      edges[r].pb({l - 1, -w});
      edges[l - 1].pb({r, w});
   }

   vi dist(k + 1, 1e9);
   dist[0] = 0;
   for (int c = 0; c <= k; c++) {
      for (int i = 0; i <= k; i++) {
         if (dist[i] == 1e9) continue;
         for (auto [to, w]: edges[i]) {
            assert(to >= 0 && to <= k);
            if (dist[to] > dist[i] + w) {
               dist[to] = dist[i] + w;
               if (c == k) {
                  cout << "NONE";
                  return;
               }
            }
         }
      }
   }
   for (int i = 1; i <= k; i++) {
      if (dist[i] - dist[i - 1]) cout << '#';
      else cout << '-';
   }
}

Tags:

Categories:

Updated:

Comments

You may also enjoy