算法至美

用户名：uq_54514514336

访问量：7757

签　名：

等　　级
排　　名	1353
经　　验	2953
参赛次数	0
文章发表	43
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1235-输出前k大的数-题解（各语言代码）
浏览：543

数列有序-题解（Python代码）
浏览：177

[编程入门]水仙花数判断-题解（各语言代码）
浏览：84

你可能喜欢

信息学奥赛一本通TT1262-挖地雷-题解（各语言代码）

　　作者: 算法至美　　　　发表时间：2022-06-28 14:17:34 浏览：153　|　评论：0　

原题链接：信息学奥赛一本通TT1262-挖地雷

用邻接表存图，从后往前递推
将经过节点的地雷数累加，找出最大值
**C++**
```cpp
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n;cin>>n;++n;
	int*a=new int [n],*v=new int [n](),*w=new int [n]();
	vector<int>*l=new vector<int>[n];
	for(int i=1;i!=n;cin>>a[i++]);
	for(int x,y;cin>>x>>y&&x&&y;l[y].push_back(x));
	for(int i=n;--i;){
		w[i]+=a[i];
		for(int j:l[i])
			if(w[i]>w[j])
				w[j]=w[v[j]=i];
	}
	int*m=max_element(w+1,w+n),x=m-w;
	for(cout<<x;x=v[x];cout<<'-'<<x);
	cout<<'\n'<<*m;
}
```
**python**
```python
n=int(input())
l=tuple(map(int,input().split()))
w=[0]*n
v=[-1]*n
c=[[] for _ in range(n)]
x,y=map(int,input().split())
while x and y:
	c[~-y].append(~-x)
	x,y=map(int,input().split())
for i in range(~-n,-1,-1):
	w[i]+=l[i]
	for j in c[i]:
		if w[i]>w[j]:
			w[j]=w[i]
			v[j]=i
n=max(w)
print(*(lambda f:f(f))(lambda f:lambda x:(-~x,)+f(f)(v[x]) if ~x else ())(w.index(n)),sep='-')
print(n)
```
**java**
```java
import java.util.Arrays;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.stream.Collectors;
public class Main {
	public static void main(String[] args) {
		final Scanner in = new Scanner(System.in);
		final int n = -~in.nextInt();
		final int[] l = new int[n], v = new int[n], w = new int[n];
		final ArrayList<ArrayList<Integer>> a = new ArrayList<>(n);
		a.add(new ArrayList<>(0));
		for (int i = 1; i != n; l[i++] = in.nextInt())
			a.add(new ArrayList<>());
		for (int x = in.nextInt(), y = in.nextInt(); x != 0 || y != 0; x = in.nextInt(), y = in.nextInt())
			a.get(y).add(x);
		in.close();
		for (int i = n; --i != 0;) {
			w[i] += l[i];
			for (int j : a.get(i))
				if (w[i] > w[j])
					w[j] = w[v[j] = i];
		}
		int m = Arrays.stream(w).max().getAsInt(), x = Arrays.stream(w).boxed().collect(Collectors.toList()).indexOf(m);
		for (System.out.print(x); (x = v[x]) != 0; System.out.print(x))
			System.out.print('-');
		System.out.println();
		System.out.print(m);
	}
}
```

0.0分

10 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

算法至美

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

字符串的输入输出处理（C语言代码）

剔除相关数（C语言代码）

三进制小数（C语言代码）

信息学奥赛一本通TT1262-挖地雷-题解（各语言代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

钟神赛车（C++代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

简单的a+b （C语言代码）

算法至美

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

字符串的输入输出处理 （C语言代码）

剔除相关数 （C语言代码）

三进制小数 （C语言代码）

信息学奥赛一本通TT1262-挖地雷-题解（各语言代码）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

钟神赛车 （C++代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

简单的a+b （C语言代码）

字符串的输入输出处理（C语言代码）

剔除相关数（C语言代码）

三进制小数（C语言代码）

　　评论区

钟神赛车（C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）