Problem: cacti_cartography (2023 finals)

Cactus Park is a famous **t**ourist attraction in Sandlandia. It holds \(N\) cactus plants, numbered from \(1\) to \(N\). The cacti are connected by \(M\) bidirectional trails, with trail \(i\) connecting cacti \(A_i\) and \(B_i\).

From any cactus, it's always possible to get to any other cactus by taking some sequence of trails. There may be cycles in the park, where a cycle is any sequence of trails that lead from a certain cactus back to itself. The park also has a special property that each trail belongs to at most one simple cycle. In graph theory terms, we can say that the Cactus Park forms a [cactus graph](https://en.wikipedia.org/wiki/Cactus_graph).

The park owners want to replace some number of cacti with information kiosks to help guide the tourists. Cutting down cactus \(i\) and building a kiosk there costs the park \(C_i\) dollars. The owners want to build enough kiosks so that the shortest path from every remaining cactus to the closest kiosk does not exceed \(K\) trails. Please help the owners determine the minimum total cost required to satisfy this requirement.

# Constraints

\(1 \le T \le 65\)
\(1 \le N \le 500\)
\(1 \le K \le \min(N, 50)\)
\(1 \le A_i, B_i \le N\)
\(A_i \ne B_i\)
\(1 \le C_i \le 10^9\)

Each unordered pair \((A_i, B_i)\) appears at most once in a given test case.

# Input Format

Input begins with a single integer \(T\), the number of test cases. For each case, there is first a line containing three integers \(N\), \(M\), and \(K\). Then, there is a line containing \(N\) integers \(C_{1..N}\). Then, \(M\) lines follow, the \(i\)th of which contains two integers \(A_i\) and \(B_i\).

# Output Format

For the \(i\)th case, output `"Case #i: "`, followed by a single integer, the minimum total cost in dollars to satisfy the park owners' requirement.

# Sample Explanation

The first case is depicted below. Replacing just cactus \(2\) would meet the requirement, but would cost \(\$10\). Instead we can replace cacti \(1\) and \(4\) for a total cost of \(\$8\).

{{PHOTO_ID:885100906409208|WIDTH:350}}

The second case is depicted below. One solution is to replace cacti \(1\) and \(4\) for a total cost of \(\$6\).

{{PHOTO_ID:3652000121792782|WIDTH:500}}

In the third case, all the cactuses are already within \(2\) trails of each other, so we just need a single kiosk anywhere. We should cut down the cheapest cactus, cactus \(1\).

{{PHOTO_ID:2643202679188960|WIDTH:350}}

In the fourth case, we can cut down cacti \(1\), \(3\), and \(6\) for a total cost of \(9 + 3 + 4 = \$16\)

{{PHOTO_ID:365613766120939|WIDTH:500}}


Sample input:
4
4 4 1
5 10 6 3
1 2
2 3
3 1
2 4
6 6 1
2 2 4 4 3 2
1 2
3 1
5 4
3 4
6 4
2 5
4 4 2
1 6 7 4
1 2
2 3
3 4
4 1
8 9 1
9 1 3 5 9 4 10 10
1 2
1 3
3 4
4 5
5 3
5 6
6 7
7 5
8 1


Sample output:
Case #1: 8
Case #2: 6
Case #3: 1
Case #4: 16


Solution: To solve this problem, let’s preprocess the input first. We'll store the input cactus graph in an adjacency list. Let’s pick any random starting vertex \(s\) from which to perform a DFS traversal, storing the pre- and post-visiting times for each vertex \(v\) as \(tin[v]\) and \(tout[v]\) respectively.

After reversing the adjacency list for each vertex, let’s repeat the DFS from the vertex \(s\) (we'll consider all adjacent vertices in reverse order this time) and store the pre- and post-visiting times for each vertex \(v\) as \(tin'[v]\) and \(tout'[v]\) respectively. Using DFS and pre/post visiting times for every edge \(u \to v\), we can determine the following:

* Whether this edge is the first or the last in its cycle when traversing the cactus starting from \(s\)
  * If \(tin[v] < tin[u]\) and \(tin'[v] < tin'[u]\), then this edge is the last of the cycle and vertex \(v\) is always the first vertex of the cycle visited on the way from vertex \(s\). Let’s denote such a vertex as a root of a cycle. Likewise, we can determine the first edge of the cycle.
* The index of the cycle this edge belongs to (or \(-1\) if it doesn’t belong to any cycle)
  * This can be done in one DFS from vertex \(s\) with an additional stack to recover the path from the first cycle’s vertex to itself.

With an additional DFS traversal from vertex \(s\), we can determine the length of each cycle and the distance from each vertex to the root of the cycle it belongs to.

For our solution, we will consider all edges as directed, in order of traversal from the starting vertex \(s\). Note that for simplicity, we can consider different traversal orders of the same cycle as two different cycles (but we'll need to mark them as interchangeable). Let’s define \(dp(e, dist1, dist2, mandatory)\), where:

* \(e\) – edge ID that uniquely identifies the start \(u\) and end \(v\) of the edge;
* \(dist1\) – distance between vertex \(v\) and the closest already placed kiosk;
* \(dist2\) – distance between vertex \(v\) and the cycle root (if edge \(e\) belongs to a cycle);
* \(mandatory\) – flag for whether we must place a kiosk in this or one of the following DP states.

The number of edges \(M\) in a cactus graph of size \(N\) is at most \(3N / 2\). Any valid distance can be up to \((2K + 1) - K\) edges from the previous kiosk, plus \(1\) edge, plus \(K\) edges to the next kiosk. The flag can take on two values, so the total number of states is approximately \(3N * (2K + 1)^2\). In addition, we can force all states with \(dist1 > K + 1\) to have \(mandatory = 1\).

For convenience, we can create a dummy edge from dummy vertex \(d\) to \(s\) and use this edge as a starting edge \(e_0\). The answer to the problem is the minimum \(dp(e_0, d1, x, 1)\) across all \(d_1\) from \(K\) to \(2K + 1\). Here, \(x\) denotes any value representing edge belonging to no cycle.

The transitions that need to be considered are the following:

1. Build a kiosk at vertex \(v\).
2. If \(dist1 < 2K + 1\), keep transitioning to the next edge without building a kiosk at \(v\). For each edge, the value of \(dist'\) will simply be \(dist1 + 1\).
3. For exactly one adjacent edge, set a new strict value of \(dist1'\) that's greater than the current \(dist1 + 1\) (set \(mandatory = 1\) for this edge). This is equal to moving the next kiosk closer to the current edge. For other edges, recompute the value of \(dist1'\) considering the kiosk at the selected edge (\(mandatory = 0\) for all such edges). This can be done in \(\mathcal{O}(K)\) by iterating over all possible values of the new \(dist1\).

As previously mentioned, the total number of states is \(\mathcal{O}(NK^2)\). Each state has \(\mathcal{O}(K)\) transitions, so the total complexity of the solution is \(\mathcal{O}(NK^3)\).


Code: #include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

typedef long long int64;

const int64 kInf = 12345678912345LL;
const int64 MAXK = 50, KLIM = (MAXK + 1) << 1, NLIM = 1000;

int N, M, K;
vector<int> weights;
vector<vector<int>> adj;
int64 f[2][KLIM][KLIM][NLIM];
int timer;
vector<int> tin, tout, par;
vector<int> cycle_ids, cycle_lens, cycle_rev, dist_to_par;
vector<vector<int>> edge_lnks;
vector<pair<int, int>> dp_edges;

void dfs(int x) {
  tin[x] = timer++;
  for (int y : adj[x]) {
    if (tin[y] != -1) {
      continue;
    }
    dfs(y);
  }
  tout[x] = timer++;
}

int cycle_counter;
vector<int> dfs_stack;

void dfs_cycles(int x, int p) {
  tin[x] = timer++;
  dfs_stack.push_back(x);
  for (int y : adj[x]) {
    if (y == p) {
      continue;
    }
    if (y == par[x]) {
      int cur_len = 1;
      int rev_cycle = -1;
      for (int z = (int)dfs_stack.size() - 1; dfs_stack[z] != par[x]; z--) {
        int edge_id = edge_lnks[dfs_stack[z - 1]][dfs_stack[z]];
        int rev_edge_id = edge_lnks[dfs_stack[z]][dfs_stack[z - 1]];
        if (rev_edge_id != -1 && cycle_ids[rev_edge_id] != -1) {
          rev_cycle = cycle_ids[rev_edge_id];
          cycle_rev[rev_cycle] = cycle_counter;
        }
        cycle_ids[edge_id] = cycle_counter;
        dist_to_par[edge_id] = cur_len++;
      }
      cycle_lens.push_back(cur_len);
      cycle_rev.push_back(rev_cycle);
      cycle_counter++;
    } else {
      if (tin[y] != -1) {
        continue;
      }
      if (edge_lnks[x][y] == -1) {
        edge_lnks[x][y] = dp_edges.size();
        dp_edges.emplace_back(x, y);
        cycle_ids.push_back(-1);
        dist_to_par.push_back(-1);
      }
      dfs_cycles(y, x);
    }
  }
  dfs_stack.pop_back();
}

int lazy_max_dist;

int64 lazy_dp(int edge_id, int dist_to_last, int par_dist, int promised) {
  if (dist_to_last > K + 1) {
    promised = 1;
  }
  if (f[promised][dist_to_last][par_dist][edge_id] != -1LL) {
    return f[promised][dist_to_last][par_dist][edge_id];
  }
  const int base_cycle_id = cycle_ids[edge_id];
  if (!dist_to_last && base_cycle_id != -1 &&
      cycle_lens[base_cycle_id] - dist_to_par[edge_id] < par_dist) {
    return f[promised][dist_to_last][par_dist][edge_id] = lazy_dp(
               edge_id, dist_to_last,
               cycle_lens[base_cycle_id] - dist_to_par[edge_id], promised);
  }
  if (!promised && base_cycle_id != -1 &&
      dist_to_par[edge_id] + par_dist < dist_to_last) {
    return f[promised][dist_to_last][par_dist][edge_id] = lazy_dp(
               edge_id, dist_to_par[edge_id] + par_dist, par_dist, promised);
  }
  const int x = dp_edges[edge_id].second;
  int64 res = kInf;
  if (dist_to_last) {
    res = min(res, lazy_dp(edge_id, 0, par_dist, 0) + weights[x]);
  }
  if (dist_to_last == lazy_max_dist) {
    return f[promised][dist_to_last][par_dist][edge_id] = res;
  }
  const int p = dp_edges[edge_id].first;
  vector<int> edge_list;
  vector<pair<int, int>> edge_groups;
  map<int, int> cycle_to_ind;
  for (int y : adj[x]) {
    if (y == p) {
      continue;
    }
    int new_edge_id = edge_lnks[x][y];
    if (new_edge_id == -1) {
      continue;
    }
    int cycle_id = cycle_ids[new_edge_id];
    if (cycle_id != -1) {
      auto mit = cycle_to_ind.find(cycle_id);
      if (mit != cycle_to_ind.end()) {
        edge_groups[mit->second].second = edge_list.size();
        edge_list.push_back(new_edge_id);
        continue;
      }
    }
    int rev_cycle_id = (cycle_id == -1 ? -1 : cycle_rev[cycle_id]);
    cycle_to_ind[rev_cycle_id] = edge_groups.size();
    edge_groups.emplace_back(edge_list.size(), -1);
    edge_list.push_back(new_edge_id);
  }
  const int esz = edge_list.size();
  if (!esz) {
    return f[promised][dist_to_last][par_dist][edge_id] =
               (promised || dist_to_last > K) ? res : 0LL;
  }
  const int egsz = edge_groups.size();
  vector<int64> edge_f(esz), edge_f2(esz);
  for (int new_dist_to_last = dist_to_last + 1, new_promised = promised;
       new_dist_to_last <= lazy_max_dist && res;
       ++new_dist_to_last, new_promised = 1) {
    const int inv_dist_to_last = lazy_max_dist - new_dist_to_last;
    const int min_dist_to_last = min(dist_to_last + 1, 2 + inv_dist_to_last);
    for (int i = 0; i < esz; ++i) {
      const int new_edge_id = edge_list[i];
      const int new_cycle_id = cycle_ids[new_edge_id];
      int new_par_dist = lazy_max_dist;
      if (new_cycle_id != -1) {
        if (new_cycle_id == base_cycle_id) {
          new_par_dist = par_dist;
          new_par_dist =
              min(new_par_dist, 1 + cycle_lens[base_cycle_id] -
                                    dist_to_par[edge_id] + inv_dist_to_last);
        } else {
          new_par_dist = min_dist_to_last - 1;
        }
      }
      edge_f[i] = lazy_dp(new_edge_id, min_dist_to_last, new_par_dist, 0);
    }
    for (int i = 0; i < esz; i++) {
      const int new_edge_id = edge_list[i];
      const int new_cycle_id = cycle_ids[new_edge_id];
      int new_par_dist = lazy_max_dist;
      if (new_cycle_id != -1) {
        if (new_cycle_id == base_cycle_id) {
          new_par_dist = par_dist;
        } else {
          new_par_dist = dist_to_last;
        }
      }
      edge_f2[i] =
          lazy_dp(new_edge_id, new_dist_to_last, new_par_dist, new_promised);
    }
    int64 f_sum = 0LL, min_diff = kInf;
    for (int i = 0; i < egsz; i++) {
      const int ind1 = edge_groups[i].first;
      int64 edge_group_f = edge_f[ind1], edge_group_f2 = edge_f2[ind1];
      const int ind2 = edge_groups[i].second;
      if (ind2 != -1) {
        edge_group_f = min(edge_group_f, edge_f[ind2]);
        edge_group_f2 = min(edge_group_f2, edge_f2[ind2]);
      }
      min_diff = min(min_diff, edge_group_f2 - edge_group_f);
      f_sum += edge_group_f;
    }
    res = min(res, f_sum + min_diff);
  }
  return f[promised][dist_to_last][par_dist][edge_id] = res;
}

int64 solve() {
  vector<pair<int, int>> edges;
  cin >> N >> M >> K;
  weights.resize(N);
  for (int i = 0; i < N; ++i) {
    cin >> weights[i];
  }
  edges.resize(M);
  for (int i = 0; i < M; ++i) {
    cin >> edges[i].first >> edges[i].second;
    --edges[i].first;
    --edges[i].second;
  }
  int root = N;
  edges.emplace_back(N++, 0);
  M++;
  adj.assign(N, {});
  for (int i = 0; i < M; i++) {
    adj[edges[i].first].push_back(edges[i].second);
    adj[edges[i].second].push_back(edges[i].first);
  }
  timer = 0;
  tin.assign(N, -1);
  tout.resize(N, -1);
  dfs(root);
  vector<int> tin0 = tin, tout0 = tout;
  for (int x = 0; x < N; x++) {
    reverse(adj[x].begin(), adj[x].end());
  }
  timer = 0;
  tin.assign(N, -1);
  tout.resize(N, -1);
  dfs(root);
  par.assign(N, -1);
  for (int x = 0; x < N; x++) {
    for (int y : adj[x]) {
      if (tin0[y] < tin0[x] && tin[y] < tin[x]) {
        par[x] = y;
      }
    }
  }
  cycle_counter = 0;
  dp_edges.clear();
  edge_lnks.assign(N, vector<int>(N, -1));
  cycle_ids.clear();
  cycle_lens.clear();
  cycle_rev.clear();
  dist_to_par.clear();
  timer = 0;
  tin.assign(N, -1);
  dfs_stack.clear();
  dfs_cycles(root, root);
  for (int x = 0; x < N; x++) {
    reverse(adj[x].begin(), adj[x].end());
  }
  timer = 0;
  tin.assign(N, -1);
  dfs_cycles(root, root);
  memset(f, -1, sizeof f);
  lazy_max_dist = ((K + 1) << 1) - 1;
  int64 res = kInf;
  for (int i = 0; i <= K; i++) {
    res = min(res, lazy_dp(edge_lnks[root][0], i + K + 1, lazy_max_dist, 1));
  }
  return res;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}