列表

详情

NC219631. Prospecting

描述

Prospectin' Pete has a lead on a new titanium mine, and needs your help pitching a mining operation to investors. The mine can be represented as a tree: the mine entrance is the root of the tree, other tree nodes are pockets of underground titanium ore, and the tree edges are potential tunnels Pete can dig between two pockets (or between the mine entrance and one pocket, for edges adjacent to the root node). The tunnel connecting the -th ore pocket to its parent has a length of  feet. One of the tree leaves contains the motherlode, and each other ore pocket contains  dollars worth of ore.

Pete begins at the mine entrance, and his goal is to reach the motherlode. Obviously, Pete cannot travel to pocket  until all  feet of dirt in the tunnel leading to it has been removed. But once a tunnel has been completely excavated, Pete can travel that tunnel, in both directions, as many times as he wants.

Pete explores the mines by repeatedly performing the following steps, in order:

  1. Pete chooses a tunnel that he can reach from his current location, and that has not yet been fully excavated.
  2. Pete digs through one foot of the chosen tunnel; this costs him one dollar.
  3. If the tunnel is now completely clear, Pete travels through the tunnel to the newly opened pocket and mines the ore. If that pocket contains the motherlode, then he stops exploring the mine. Otherwise, he sells the ore in that pocket for  dollars and continues exploring.

Note that the tunnel Pete chooses to dig in the first step of each round of digging does not need to be adjacent to his current location, so long as Pete can reach the tunnel by traveling through the mine along a sequence of completely-excavated tunnels. He can also choose a different tunnel each round, even if the tunnel he was digging in the previous round is not yet completely excavated. If Pete ends a round of digging with no money, and without having reached the motherlode, the mining operation is a bust and Pete goes home bankrupt.

Pete has surveyed the geology of the area and knows the mine layout, as well as the amount of ore in each chamber, but hasn't yet decided on a strategy for how to dig the tunnels. He knows that in addition to any riches he earns from the mine itself, he will need some amount of startup money in order to reach the motherlode, and so he is courting investors. He wants to present them with two pieces of information:

  • The minimum number of dollars  that Pete must begin with in order for his venture to be successful even in the worst-case: for it to be guaranteed that he reaches the motherlode no matter how he chooses the tunnel to excavate during each round of digging.

This information will allow the investors to decide how much to fund Pete, based on how much they trust him to dig optimally without making any mistakes.

Given the mine layout, compute  and .


Figure F.1: Illustrations of sample inputs  (on the left) and . Edges represent tunnels and nodes represent ore pockets. Ore values  in each pocket and length  of each tunnel are written in black text ("ML" stands for the motherlode). Nodes are labeled in red with their indices.

输入描述

The first line of input contains an integer , the number of nodes in the tree representing Pete's mine. The remaining input consists of  lines, the th of which (starting at ) contains three integers , , and  encoding information about the th node of the tree.  is the index of the th node's parent in the tree. A parent index of zero means that the node's parent is the mine entrance (root of the tree).  is the value of the ore in node , and  is the length of the tunnel connecting node  to node . Exactly one node has , indicating that the node contains the motherlode; all other inputs satisfy .

Note that node zero is the mine entrance; it contains no ore and has no corresponding line in the input. You may assume that the motherlode is a leaf of the tree (no node has the motherlode node as a parent).

输出描述

Print two space-separated integers  and , the worst-case and best-case investment Pete needs in order to clear a path to the motherlode, as described in more detail above.

示例1

输入: 

5
0 3 1
0 0 2
2 -1 1
2 0 5

输出: 

8 1

示例2

输入: 

5
0 -1 4
0 2 1
0 4 3
0 3 2

输出: 

7 1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 140ms, 内存消耗: 15556K, 提交时间: 2021-03-23 13:52:51 

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fors(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
typedef pair<int,int> pii;
const int maxn = 2e5 + 50;
int x[maxn], y[maxn],n;
vector<int> g[maxn];
const int inf = 0x3f3f3f3f;
void init() {
	scanf("%d", &n);
	fors(i,1,n) {
		int p;
		scanf("%d%d%d", &p, &x[i], &y[i]);
		if(x[i] == -1) x[i] = inf;
		g[p].pb(i);
	}
}
int dfs_worst(int u) {
	int res = y[u] - x[u];
	for(int v: g[u])
		res += dfs_worst(v);
	return max(res, y[u]-1);
}
int it[maxn], p[maxn];
int dfs(int u) {
	int invest=inf;
	p[u]=x[u]-y[u];
	for(auto v:g[u]) {
		p[u]+=max(0,dfs(v));
		if(p[v]>0) invest=min(invest,it[v]);
	}
	it[u]=y[u]<x[u]?y[u]:max(y[u],y[u]-x[u]+invest);
	return p[u];
}
int dfs_best() {
	int cur,money(0),cost(0);
	priority_queue<pii,vector<pii>,greater<> >que;
	dfs(0);
	que.emplace(0,0);
	do{
		cur=que.top().second;
		que.pop();
		cost=max(cost,y[cur]-money);
		money+=x[cur]-y[cur];
		for(auto v:g[cur]) if(p[v]>0) que.emplace(it[v],v);
	}while(x[cur]!=inf);
	return cost;
}
int main() {
	init();
	printf("%d %d\n",dfs_worst(0)+1,dfs_best());
}
/*
5
0 100 9
0 0 6
2 -1 6
2 4 2
*/

上一题

© 2025 nowcoder.com