Problem: second_flight (2022 quals)

**Note: This problem has large input, so we recommend pre-downloading the compressed zip file.**

Meta Getaways is a travel agency that deals with \(N\) airports numbered \(1...N\), and \(M\) flight paths. Flight path \(i\) connects airports \(A_i\) and \(B_i\) in both directions, with two direct flights operating every morning (one in each direction), and another two every evening (also one in each direction). Each of these four direct flights can carry up to \(C_i\) **t**ourists.

{{PHOTO_ID:356437426702208|WIDTH:400}}

The first sample case is depicted above, with morning and evening flights in red and blue.

Peak travel season is here, and will last \(Q\) days. For each day \(i\), determine \(F_i\), the maximum number of tourists who could possibly fly from airport \(X_i\) to \(Y_i\). Each tourist may either fly directly or take one morning and one evening flight which share an intermediate airport.


# Constraints

\(1 \leq T \leq 70 \)
\(1 \leq N, M, Q \leq 200{,}000\)
\(1 \leq C_i \leq 10^9 \)
\(1 \leq A_i, B_i \leq N; A_i \ne B_i \)
\(1 \leq X_i, Y_i \leq N; X_i \ne Y_i\)
All unordered pairs \((A_i, B_i)\) within a given test case are distinct.

The sum of \(Q\) across all test cases is at most \(5{,}000{,}000\).


# Input Format

Input begins with a single integer \(T\), the number of test cases. For each case, there is first a line containing three space-separated integers \(N\), \(M\), and \(Q\). Then, \(M\) lines follow, the \(i\)th of which contains three space-separated integers \(A_i\), \(B_i\), and \(C_i\). Then, \(Q\) lines follow, the \(i\)th of which contains two space-separated integers \(X_i\) and \(Y_i\).


# Output Format

For the \(i\)th case, print a line containing "`Case #i:` " followed by \(Q\) space-separated integers \(F_1, ..., F_Q\).


# Sample Explanation

In the first case:

- On day \(1\), we must send as many tourists from airport \(1\) to airport \(2\). We can fly \(10\) tourists direct in the morning and \(10\) more at night. Only \(5\) tourists can be flown from \(1 \to 3\) in the morning and \(3 \to 2\) in the evening (despite the evening flight capacity being \(15\)). Therefore, \(F_1 = 10 \cdot 2 + 5 = 25\).
- On day \(2\), we can fly \(5\) tourists direct in the morning and evening, then fly \(10\) tourists through airports \(1 \to 2 \to 3\). Therefore, \(F_2 = 5 \cdot 2 + 10 = 20\).
- \(F_3 = 15 \cdot 2 + 5 + 7 = 42\)
- \(F_4 = 10 \cdot 2 + 7 = 27\)
- \(F_5 = 7 \cdot 2 + 10 = 24\)
- On day \(6\), there are no direct flights. We can fly \(10\) tourists through airports \(4 \to 2 \to 1\), and \(5\) tourists through airports \(4 \to 3 \to 1\) for a total of \(F_6 = 10 + 5 = 15\) tourists.

In the second case:

- \(F_1 = 10 \cdot 2 + 20 = 40\)
- \(F_2 = 30 \cdot 2 + 10 = 70\)
- \(F_3 = 0\)
- \(F_4 = 20 \cdot 2 + 10 = 50\)
- \(F_5 = 0\)
- \(F_6 = 0\)



Sample input:
3
4 5 6
1 2 10
1 3 5
2 3 15
2 4 10
3 4 7
1 2
1 3
2 3
2 4
3 4
4 1
4 3 6
1 2 10
2 3 20
3 1 30
1 2
1 3
1 4
2 3
2 4
3 4
4 3 6
1 2 20
2 3 10
3 4 30
1 2
1 3
1 4
2 3
2 4
3 4


Sample output:
Case #1: 25 20 42 27 24 15
Case #2: 40 70 0 50 0 0
Case #3: 40 10 0 20 10 60


Solution: # Solution 1 (`second_flight.cpp`):

For each query, we'll start by checking if that direct edge exists. If it does, we'll add that to the query's answer twice (once for morning, once for evening). Note that that edge will never be present in a path of length \(2\).

To calculate the contribution to the answer of paths with length exactly \(2\), we'll always process each query from the node with the higher degree.

For nodes with degree over \(\sqrt M\) (which we'll call "big" nodes), we can precompute the max flow to all possible indirect destinations by traversing all \(2\)-steps. This uses each of the \(M\) edges at most once per big node. As there can be at most \(\sqrt M\) such big nodes, the overall running time for the precomputation is \(\mathcal{O}(M^{1.5})\). We can later look up queries involving a big node in \(\mathcal{O}(1)\).

For nodes with degree under \(\sqrt M\) (which we'll call "small" nodes), all queries assigned to them will be between two small nodes. For each such query, we can loop through the intersection of the sets of neighbors for both nodes, directly summing the max flows in \(\mathcal{O}(\sqrt M)\) time.

Therefore, the overall running time is bounded by \(\mathcal{O}((N+M+Q)^{1.5})\).


# Solution 2 (`second_flight_alt.cpp`):

Consider the following basic algorithm for answering queries, where \(\text{adj}[a]\) is a hash table of incident edges \((a, b)\), with flight capacity \(\text{adj}[a][b] = c\):

```
def query(adj[][], x, y):
  F = 0

  if adj[x] contains an edge to y:
    F += 2*adj[x][y]  # Fly direct x -> y

  for each edge (x -> mid) in adj[x]:
    if adj[mid] contains edge (mid -> y):
      F += min(adj[x][mid], adj[mid][y])  # Fly indirect x -> mid -> y

  return F
```

Since a given \(\text{adj}[x]\) can hold \(\mathcal{O}(M)\) edges, \(Q\) queries take \(\mathcal{O}(MQ)\) for-loop steps (hash table lookups). We claim that this drops to \(\mathcal{O}((M + Q)^{1.5})\) with the two simple optimizations below:

- Memoize the answer across all unordered query pairs.
- Always process indirect flights from the query node with the lower degree.

The former means we only need to process \(\min(Q, \frac{N(N - 1)}{2})\) distinct queries. The latter means each query \((x, y)\) runs in \(\mathcal{O}(\min(d_x, d_y))\) steps, where \(d_i\) is the degree of node \(i\).

It is well known that the sum of all nodes' degrees in a simple graph is twice the number of edges. This is because a node's degree is the number of edge "endpoints" assigned to it. We can thus think of the set of degrees of all nodes as a size \(N\) partition of the \(2M\) endpoints.

The number of steps is bounded by the max possible sum of \(\min(d_x, d_y)\) over \(\min(Q, \frac{N(N - 1)}{2})\) distinct unordered query pairs \((x, y)\), for all possible degree partitions \(d_1 + ... + d_N = 2M\). Without loss of generality, assume the partitions are sorted \(d_1 \ge \cdots \ge d_N\). Thus the bound is:

\[\begin{aligned}&\begin{array}{ccccccc}\min(d_1, d_2) &+& \min(d_1, d_3) &+&\cdots&+& \min(d_1, d_N) \\ &+& \min(d_2, d_3) &+&\cdots &+& \min(d_2, d_N) \\[5pt] & &  & &\ddots & & \vdots \\ & & & & &+&\min(d_{N-1}, d_N) \end{array}\\&\begin{array}{ccccccc}= d_2 &+& d_3 &+&\cdots&+& d_N \\ &+& d_3 &+&\cdots &+& d_N \\[5pt] & &  & &\ddots & & \vdots & \kern{49pt}\\ & & & & &+& d_N\end{array}\end{aligned}\]

If we were to pick the \(Q\) largest terms here, we should pick the first \(k - 1\) column(s), where:

\[k = \begin{cases}O(\sqrt{Q}) &\text{if } Q \le \frac{N(N - 1)}{2} \\[5pt] N &\text{if } Q > \frac{N(N - 1)}{2} \end{cases}\]

Note that in both cases, \(k = \mathcal{O}(\sqrt{Q})\). We'll have to maximize \(1 \, d_2 + 2 \, d_3 + \cdots + (k-1)\,d_k\) by distributing \(2M\) endpoints among \(d_{1..k}\), while setting each \(d_{(k+1)..N} := 0\).

Fixing \(k\), we see that the importance of maximizing \(d_i\) increases with \(i\), as the "weights" of \(d_i\) increase with \(i\). However as \(d_i\)'s must be non-increasing, it can be shown that the max is attained when all \(d_i\)'s are equal (*). Setting each \(d_{1..k} := \frac{2M}{k}\), we get a bound of:

\[\begin{aligned}&(1 + 2 + ... + k-1)\cdot\frac{2M}{k}\\&= \frac{(k-1)(k-2)}{2} \cdot \frac{2M}{k} \\ &= \mathcal{O}(Mk) \\ &= \mathcal{O}(M \sqrt Q) \kern{20pt}(\text{since }k = \mathcal{O}(\sqrt Q))\end{aligned}\]

(*) **Note**: Maximizing the expression can be formulated as the following linear program:

Maximize \(1\,d_2 + 2\,d_3 + \cdots + (k-1)\,d_k\), subject to \(d_i \ge 0\), and:

\[\begin{array}{rcl} d_1 + d_2 + \cdots + d_{k} &\le& 2M \\[3pt] d_1 - d_2 &\ge& 0 \\[3pt] d_2 - d_3 &\ge& 0 \\[5pt] & \vdots & \\[3pt] d_{k-1} - d_k &\ge& 0 \end{array}\]

Using LP methods, it can be verified that the max is attained when every \(d_i = \frac{2M}{k}\).

[See David Harmeyer's solution video here.](https://youtu.be/AbF6-TtkPLs)



Code: #include <cmath>
#include <iostream>
#include <unordered_map>
using namespace std;

const int LIM = 200000;

int N, M, Q;
unordered_map<int, int> adj[LIM];

// big_ind_flow[u][v] = the total flow from u to v through length-2 paths
// if u is a "big" node with degree > sqrt(M), otherwise big_ind_flow[u] = {}.
unordered_map<int, long long> big_ind_flow[LIM];

inline int degree(int i) {
  return adj[i].size();
}

inline bool is_big(int i) {
  return degree(i) > (int)sqrt(M);
}

void solve() {
  for (int i = 0; i < LIM; i++) {
    adj[i].clear();
    big_ind_flow[i].clear();
  }
  cin >> N >> M >> Q;
  for (int i = 0, a, b, c; i < M; i++) {
    cin >> a >> b >> c;
    a--, b--;
    adj[a][b] = adj[b][a] = c;
  }
  // O(M^1.5) - precompute length-2 max flows for "big" nodes (deg > sqrt(M)).
  for (int u = 0; u < N; u++) {
    if (is_big(u)) {
      for (auto const &[mid, c1] : adj[u]) {
        for (auto const &[v, c2] : adj[mid]) {
          if (u != v) {
            big_ind_flow[u][v] += min(c1, c2);
          }
        }
      }
    }
  }
  // Answer queries.
  for (int i = 0, x, y; i < Q; i++) {
    cin >> x >> y;
    x--, y--;
    if (degree(x) < degree(y)) {
      swap(x, y);  // Always process queries from bigger node.
    }
    long long ans = 0;
    if (adj[x].count(y)) {
      ans += 2*adj[x][y];  // Fly direct x -> y.
    }
    if (is_big(x)) {
      ans += big_ind_flow[x][y];
    } else {
      for (auto const &[mid, c1] : adj[x]) {  // O(sqrt(M))
        if (adj[mid].count(y)) {
          ans += min(c1, adj[mid][y]);  // Fly indirect x -> mid -> y.
        }
      }
    }
    cout << " " << ans;
  }
}

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