#PU1476. USACO 2025 January Contest, Platinum — Problem 1. DFS Order

    ID: 1563 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan25来源:usaco.orgscoring:equal_test_cases搜索

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 1…N1\dots N (2≤N≤7502\le N\le 750). She generates a depth-first search (DFS) order of the graph by calling the function dfs(1)\texttt{dfs}(1), defined by the following C++ code. Each adjacency list (adj[i]\texttt{adj}[i] for all 1≤i≤N1\le i\le N) 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 (i,j)(i,j) satisfying 1≤i<j≤N1\le i<j\le N, you are given an integer ai,ja_{i,j} (0<∣ai,j∣≤10000<|a_{i,j}|\le 1000) such that If ai,j>0a_{i,j}>0, edge (i,j)(i,j) is not currently in the graph, and can be added for cost ai,ja_{i,j}. If ai,j<0a_{i,j}<0, edge (i,j)(i,j) is currently in the graph, and can be removed for cost −ai,j-a_{i,j}. Determine the minimum total cost to change the graph so that [1,2…,N][1,2\dots,N] is a possible DFS ordering.

输入格式

The first line contains NN. Then N−1N-1 lines follow. The j−1j-1th line contains a1,j,a2,j,…,aj−1,ja_{1,j}, a_{2,j}, \dots, a_{j-1,j} separated by spaces.

输出格式

The minimum cost to change the graph so that [1,2,…,N][1,2,\dots, N] is a possible DFS ordering.

数据范围

Inputs 4-9: All ai,j>0a_{i,j}>0 Inputs 10-16: N≤50N\le 50 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$.