#PU1476. USACO 2025 January Contest, Platinum — Problem 1. DFS Order
USACO 2025 January Contest, Platinum — Problem 1. DFS Order
USACO 2025 January Contest, Platinum — Problem 1. DFS Order
题目描述
Bessie has a simple undirected graph with vertices labeled (). She generates a depth-first search (DFS) order of the graph by calling the function , defined by the following C++ code. Each adjacency list ( for all ) may be permuted arbitrarily before starting the depth first search, so a graph can have multiple possible DFS orders. vector vis(N + 1); vector<vector> adj(N + 1); // adjacency list vector dfs_order;
void dfs(int x) { if (vis[x]) return; vis[x] = true; dfs_order.push_back(x); for (int y : adj[x]) dfs(y); } You are given the initial state of the graph as well as the cost to change the state of each edge. Specifically, for every pair of vertices satisfying , you are given an integer () such that If , edge is not currently in the graph, and can be added for cost . If , edge is currently in the graph, and can be removed for cost . Determine the minimum total cost to change the graph so that is a possible DFS ordering.
输入格式
The first line contains . Then lines follow. The th line contains separated by spaces.
输出格式
The minimum cost to change the graph so that is a possible DFS ordering.
数据范围
Inputs 4-9: All Inputs 10-16: Inputs 17-23: No additional constraints. Problem credits: Benjamin Qi
样例
样例 1
4
1
2 3
40 6 11
10
Initially, the graph contains no edges. $(1,2),(2,3),(2,4)$ can be added for a
total cost of $1+3+6$. The graph now has two possible DFS orderings:
$[1,2,3,4],[1,2,4,3]$.
样例 2
5
-1
10 -2
10 -7 10
-6 -4 -5 10
5
Initially, the graph contains edges $(1,2),(2,3),(2,4),(1,5),(2,5),(3,5)$. Edge
$(3,5)$ can be removed for a cost of $5$.
样例 3
4
-1
-2 300
4 -5 6
9
Initially, the graph contains edges $(1,2),(1,3),(2,4)$. Edge $(2,4)$ can be
removed and edge $(1,4)$ can be added for a total cost of $5+4=9$.