A millennium from now, Earth, designated as Planet 1, stands on the brink of resource…
- User
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 the 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 an one integer t , indicating the number of testcases. Each testcase 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≤t≤20
2≤p≤500
1≤w≤1000
1≤pi,pj≤p
Output For each testcase, 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
- Assistant
To solve this problem, we need to find the maximum number of edge-disjoint paths from Earth (Planet 1) to the Sanctuary Planet (Planet ( p )) in a given directed graph. This is equivalent to finding the maximum flow in a network with capacities set to the number of wormholes (which can be more than one between the same two planets due to potential multiple wormholes connecting them).
Here's how you can approach the problem:
-
Model the Problem as a Network Flow:
-
Nodes and Edges:
- Each planet is a node in the graph.
- Each wormhole is a directed edge from ( pi ) to ( pj ).
-
Edge Capacities:
- Since each wormhole can only be used once and collapses after use, each edge has a capacity of 1.
- If there are multiple wormholes between the same two planets, the capacity of the edge is the number of wormholes.
-
-
Find the Maximum Flow:
- Use an efficient max-flow algorithm suitable for the given constraints (planets ( p \leq 500 ) and wormholes ( w \leq 1000 )).
- Dinic’s algorithm is efficient for such problems and works well with networks where capacities are integers (capacities of wormholes are integers and relatively small).
-
Implementation Details:
-
Graph Representation:
- Use an adjacency list to represent the graph.
- For each edge, store the capacity and a reference to its reverse edge to facilitate capacity updates during the algorithm.
-
Algorithm Steps:
- Level Graph Construction (BFS):
- Build levels of nodes starting from the source (Planet 1). If the sink (Planet ( p )) is not reached, there are no more augmenting paths.
- Blocking Flow Computation (DFS):
- Find augmenting paths using DFS that respect the levels established.
- Update capacities along the path and reverse edges accordingly.
- Level Graph Construction (BFS):
-
-
Output the Result:
- The maximum flow value obtained from the algorithm is the maximum number of edge-disjoint paths, which corresponds to the maximum number of days you can guide the last population to safety.
Below is the implementation of the solution using Dinic's algorithm in Python:
def dinic(): import sys import threading def main(): import sys sys.setrecursionlimit(1 << 25) t = int(sys.stdin.readline()) for _ in range(t): p, w = map(int, sys.stdin.readline().split()) n = p m = w edges = [] adj = [[] for _ in range(n)] for _ in range(m): a, b = map(int, sys.stdin.readline().split()) u = a - 1 # adjust to 0-based indexing v = b - 1 # Since multiple wormholes can exist between the same planets, # we sum capacities between the same nodes. edge_found = False for idx, edge_idx in enumerate(adj[u]): edge = edges[edge_idx] if edge['to'] == v: edge['capacity'] +=1 edges[edges[edge_idx]['rev']]['capacity'] +=0 # reverse edge capacity remains 0 edge_found = True break if not edge_found: # Forward edge edges.append({'to': v, 'rev': len(adj[v]), 'capacity': 1}) adj[u].append(len(edges)-1) # Reverse edge edges.append({'to': u, 'rev': len(adj[u])-1, 'capacity': 0}) adj[v].append(len(edges)-1) source = 0 sink = n - 1 max_flow = 0 level = [0]*n def bfs(): from collections import deque nonlocal level level = [-1]*n queue = deque() queue.append(source) level[source] = 0 while queue: v = queue.popleft() for idx in adj[v]: e = edges[idx] if e['capacity'] > 0 and level[e['to']] < 0: level[e['to']] = level[v] + 1 queue.append(e['to']) return level[sink] != -1 iter = [0]*n def dfs(v, upTo): if v == sink: return upTo for i in range(iter[v], len(adj[v])): e_idx = adj[v][i] e = edges[e_idx] if e['capacity'] > 0 and level[v] < level[e['to']]: d = dfs(e['to'], min(upTo, e['capacity'])) if d >0: e['capacity'] -= d edges[e_idx ^1]['capacity'] += d return d iter[v] +=1 return 0 INF = float('inf') flow = 0 while bfs(): iter = [0]*n f = dfs(source, INF) while f > 0: flow += f f = dfs(source, INF) print(flow) threading.Thread(target=main, ).start() -