Mission to Guide Humanity to Sanctuary
A millennium from now, Earth, designated as Planet 1, stands on the brink of resource exhaustion. To ensure the survival of the human race, humanity has advanced not only in scientific knowledge but has also expanded its reach to various planets across distant galaxies. So far, p planets have been identified as suitable for human habitation. Other than Earth, there exists only one, the pth planet, that can act as humanity's final sanctuary.
These planets are connected by a network of w wormholes that enable instantaneous travel between them, but the wormholes are one-way, allowing travel from one planet to another without the possibility of reverse travel. The challenge lies in safely guiding the last remaining population from Earth to the Sanctuary Planet using the limited wormhole connections available.
As the mission commander, you must navigate your spaceship each day from Earth to the Sanctuary, but each wormhole is highly unstable and can only be used once before it collapses into a singularity.
To prepare for the worst-case scenario, you need to calculate the maximum number of days you can successfully lead humanity's last population to safety. Each day, you must find a unique path through the wormholes, ensuring that no wormhole is used more than once throughout the entire mission.
Input
The first line contains one integer t, indicating the number of test cases. Each test case is as follows:
- The first line contains two space-separated integers p and w; where p is the number of planets, marked from 1 to p, and w is the number of wormholes.
- The next w lines each contain two space-separated integers pi and pj, indicating a wormhole between the planets pi and pj.
Constraints
- $1 \leq t \leq 20$
- $2 \leq p \leq 500$
- $1 \leq w \leq 1000$
- $1 \leq pi, pj \leq p$
Output
For each test case, print one integer, the maximum number of days required to successfully guide the population to safety.
Example
Input: 1 4 5 1 2 1 3 2 3 2 4 3 4 Output: 2
Explanation
The following is the flow network of the given test case:
If you choose the path 1−2−3−4 to go from Earth to the Sanctuary planet, it would take you 1 day to guide the population to safety. But since we are doing a worst-case scenario preparation, we need to check if there are other ways to navigate.
If you take the path 1−2−4 on day 1, the wormholes from 1−2 and 2−4 collapse. On day 2, if you take path 1−3−4, the wormholes from 1−3 and 3−4 collapse. Then the number of days it would take to guide the population to safety is 2.
After that, no more wormholes will remain to navigate from Earth to the Sanctuary as they will have collapsed into singularity, so the maximum number of days taken will be 2.
Solution
#include <bits/stdc++.h> // Includes all standard libraries in one go for faster coding
using namespace std; // Simplifies code by eliminating the need to prefix std functions
typedef long long ll; // Defining a shorter alias 'll' for long long type for convenience
typedef vector<int> vi; // Defining 'vi' as a shorthand for vector of integers
typedef pair<int, int> ii; // Defining 'ii' as a shorthand for a pair of two integers
const int MAXN = 505; // Maximum number of nodes that the graph can have
const ll INF = 1e18; // A large constant used to represent infinity in terms of flow capacity
// Structure to represent an edge in the flow network
struct Edge {
int to, rev; // 'to' is the destination node, 'rev' is the index of the reverse edge
ll cap, flow; // 'cap' is the capacity of the edge, 'flow' is the current flow through the edge
};
vector<Edge> edges; // Vector to store all edges in the flow network
vector<vi> adj; // Adjacency list to store edges for each node, using their index in the 'edges' vector
vi level, ptr; // 'level' stores level of each node in the BFS phase, 'ptr' helps optimize DFS by remembering edges
// Function to add an edge between nodes 'u' and 'v' with a given capacity 'cap'
void addEdge(int u, int v, ll cap) {
// Add forward edge from 'u' to 'v' with given capacity, and a reverse edge with zero capacity
edges.push_back({v, (int)edges.size() + 1, cap, 0});
edges.push_back({u, (int)edges.size() - 1, 0, 0});
// Store the indices of the edges in the adjacency list
adj[u].push_back((int)edges.size() - 2);
adj[v].push_back((int)edges.size() - 1);
}
// Breadth-first search (BFS) to construct level graph from source 's' to sink 't'
bool bfs(int s, int t) {
level.assign(MAXN, -1); // Initialize all node levels to -1 (unvisited)
level[s] = 0; // Set the source node level to 0
queue<int> q; // Queue for BFS
q.push(s); // Start BFS from the source node
while (!q.empty()) {
int u = q.front(); // Get the front node from the queue
q.pop();
// Traverse all edges connected to node 'u'
for (int i : adj[u]) {
Edge &e = edges[i]; // Reference the edge using its index
// If there's remaining capacity and the destination node is unvisited, update its level
if (e.cap - e.flow > 0 && level[e.to] == -1) {
level[e.to] = level[u] + 1; // Level of the next node is one more than the current node
q.push(e.to); // Push the node into the queue to continue BFS
}
}
}
return level[t] != -1; // Return true if we reached the sink node, false otherwise
}
// Depth-first search (DFS) to find augmenting paths and push flow from node 'u' to sink 't'
ll dfs(int u, int t, ll flow) {
if (u == t) return flow; // If we reach the sink node, return the flow
// Traverse all adjacent edges using the pointer 'ptr' to avoid revisiting edges
for (int &i = ptr[u]; i < (int)adj[u].size(); ++i) {
Edge &e = edges[adj[u][i]]; // Reference the edge
// If there's remaining capacity and the next node is at the next level in the BFS tree
if (e.cap - e.flow > 0 && level[e.to] == level[u] + 1) {
// Recursively try to push flow through the next node
ll pushed = dfs(e.to, t, min(flow, e.cap - e.flow));
if (pushed > 0) { // If flow was successfully pushed
e.flow += pushed; // Update the current edge's flow
edges[e.rev].flow -= pushed; // Update the reverse edge's flow
return pushed; // Return the amount of flow pushed
}
}
}
return 0; // If no flow could be pushed, return 0
}
// Dinic's algorithm to compute maximum flow from source 's' to sink 't'
ll dinic(int s, int t) {
ll max_flow = 0; // Variable to store the maximum flow
// While there's a path from source to sink in the level graph
while (bfs(s, t)) {
ptr.assign(MAXN, 0); // Reset the pointer array for DFS
// Try to push flow while there's an augmenting path
while (ll pushed = dfs(s, t, INF)) {
max_flow += pushed; // Add the flow pushed to the total max flow
}
}
return max_flow; // Return the total maximum flow
}
int main() {
ios_base::sync_with_stdio(false); // Optimize input/output for faster processing
cin.tie(NULL); // Untie cin and cout for faster input/output
int t; // Number of test cases
cin >> t; // Input the number of test cases
while (t--) { // Process each test case
int p, w; // 'p' is the number of nodes, 'w' is the number of edges
cin >> p >> w; // Input the number of nodes and edges
edges.clear(); // Clear the previous test case's edges
adj.assign(p + 1, vi()); // Reinitialize the adjacency list
level.assign(p + 1, -1); // Reinitialize the level array
// Input the edges and add them to the graph
for (int i = 0; i < w; ++i) {
int pi, pj; // Nodes connected by the edge
cin >> pi >> pj; // Input the edge between nodes pi and pj
addEdge(pi, pj, 1); // Add an edge with capacity 1 (representing a path or road)
}
ll max_days = dinic(1, p); // Compute the maximum number of days using Dinic's algorithm
cout << max_days << endl; // Output the result for the current test case
}
return 0; // Return 0 to indicate successful program execution
}
Explanation
The problem can be modeled as a flow network where each planet is represented as a node and each wormhole is represented as an edge with a capacity of 1. The goal is to find the maximum flow from the source node (Earth) to the sink node (Sanctuary) while ensuring that each edge is used only once.
Complexity Analysis
The time complexity of the Dinic's algorithm used in this solution is $O(V^2E)$, where $V$ is the number of nodes and $E$ is the number of edges in the flow network. In the worst case, the algorithm can run in $O(V^2E)$ time, which is efficient for the given constraints.
Sample Solution Provided by Instructor