BOJ 7577 - 탐사

BOJ 7577 - 탐사

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

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

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

$s_i - s_0 \le i$ 에서 한 개의 부등식이 나온다.

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

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

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

이 문제는 $s_0 \sim s_k$ 까지 총 $k+1$ 개의 정점을 만들고 $s_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 << '-';
   }
}