This problem involves finding optimal emergency rescue routes through a network of cities. Given a map with cities, roads, and rescue teams, the objective is to reach a destination city via shortest path while maximizing the number of rescue teams gathered along the way. Input Specifications: First...
A. [POI2004] SZP Description Given a directed graph with cycles, where each node has exactly one outgoing edge (non-self-loop), select the maximum number of nodes such that every selected node has at least one immediate predecessor that is not selected. Solution Observe that each weakly connected co...
Dynamic Graph Connectivity When adding a new edge between two nodes in a graph, all bridge edges along the path between those nodes become non-bridge edges. This observation leads to efficient updates using tree decomposition techniques or more straightforward approaches like edge contraction. The f...
Problem 1: Freshman Challenge The answer is a constant value. #include <cstdio> int main() { printf("%d\n", 15); return 0; } Problem 2: Flooring We only need the product of the dimensions to be divisible by 6, and both dimensions must be large enough for a 2×3 or 3×2 tile. #include &...
Negative Cycle DetectionWhen detecting negative cycles reachable from a starting node, two primary algorithms are used: Bellman-Ford and SPFA (Shortest Path Faster Algorithm).In the Bellman-Ford algorithm, shortest paths are computed over n-1 iterations. If a relaxation is still possible during the...
String Character AnnihilationWhen two distinct characters in a string annihilate each other, the specific identity of the characters is irrelevant. As long as multiple distinct characters exist, they can be paired off. The goal of minimizing the remaining characters can be modeled as a two-pile stac...
Problem A Given an n×m matrix of 0s and 1s, you can flip any submatrix. Find the minimum number of operations to create a path from the top-left corner to the bottom-right corner that only moves down or right and traverses only 0s. (n,m\le 1000). This is a straightforward dynamic programming problem...
Dynamic Programing Coin Change Problem def coin_change(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0 for coin in coins: for x in range(coin, amount + 1): dp[x] = min(dp[x], dp[x - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1 Predict the Winner def predict_winner(...
Shortest Paths Revisited via Floyd-Warshall The problem Luogu P1119 (Post‑Disaster Reconstruction) provides a natural opportunity to exploit the transitive nature of the Floyd‑Warshall algorithm. We are given a graph where certain vertices become usable over time and must answer online queries about...
Original Model and Related Concepts of Bipartite Graphs A bipartite graph, also known as a bigraph, is a special model in graph theory. Let G = (V, E) be an undirected graph. If the vertex set V can be partitioned into two disjoint subsets (A and B), and every edge (i, j) in the graph connects verti...
