L2-059 森林藏宝图 - java

L2-059 森林藏宝图语言时间限制内存限制代码长度限制栈限制Java (javac)1200 ms512 MB16KB8192 KBPython (python3)500 ms256 MB16KB8192 KB其他编译器400 ms64 MB16KB8192 KB题目描述姥姥手里有一张森林藏宝图别问怎么得到的图中标记了森林的入口还画了通往多个藏宝地的小路。画这张藏宝图的人还贴心地为每条小路标记了一个“安全系数”是区间[ 0 , 100 ] [0,100][0,100]中的整数。为了方便规划姥姥给每个有分叉的路口、以及每个藏宝地都做了编号其中森林的入口编号为0 00。略加研究后姥姥有了一个重要的发现如果我们一路向前不走回头路那么从0 00号入口到每个藏宝地的路径都不是存在且唯一的换言之我们不可能从两条不同的岔路殊途同归地走到同一个藏宝地。此外从入口沿任何一条小路一直走到尽头都会到达一个藏宝地。姥姥不打算冒太大风险所以只打算沿着安全系数比较大的路走。本题就请你帮个忙看看如果只考虑途经最小的安全系数最大的路径有可能取到哪些宝藏即从0 00号入口到该藏宝地路径上所有小路安全系数的最小值最大。声明本题仅限人类解答。输入格式输入在第一行给出图中标记的顶点总数n 1 n ≤ 10 5 n1 n \le 10^5 n1n≤105—— 如题面所述森林的入口编号为0 00其它节点分叉路口和藏宝地的编号从1 11到n − 1 n−1n−1。随后n − 1 n−1n−1行第i 1 ≤ i n i1 \le i ni1≤in行给出编号为i ii的节点的前驱节点的编号j jj、以及从j jj到i ii这条小路的安全系数s j i 0 ≤ s j i ≤ 100 s_{ji} 0 \le s_{ji} \le 100sji​0≤sji​≤100。一行中的数字间以空格分隔。注所谓节点i ii的“前驱节点”是指从0 00号入口出发到达i ii之前所到达的那个节点。因为从0 00号入口到每个藏宝地的路径都是不唯一的容易证明每个节点的前驱节点也不是唯一的。输出格式首先在第一行输出解的途经最小安全系数的最大值 —— 所谓“解”即按题目要求给姥姥推荐的藏宝地也就是从0 00号入口出发到该藏宝地路径上所有小路安全系数的最小值最大。第二行按非递增顺序输出解的编号。编号间以一个空格分隔行首尾不得有多余空格。输入样例90 300 100 01 81 152 204 405 10输出样例106 8在给定的单向图中找到从0开始到每个藏宝地后该路径的安全系数最小值组最大。由上图可以发现藏宝地依次为7, 8, 6, 3。到藏宝地7中其小路上安全系数的最小值为8到藏宝地8中其小路上安全系数的最小值为10到藏宝地6中其小路上安全系数的最小值为10到藏宝地3中其小路上安全系数的最小值为0那么到所有藏宝地中所有小路上的安全系数最小值最大为10, 那么选择的藏宝点为6, 8。emmmmmmm简单图论搜索题目由于该图是有向图且保证不会回头。那么可以直接用bfs往下一直搜索并且记录一下到当前节点时最小的值是多少。然后如果无法继续往下搜索了那么则表示当前这个节点是藏宝点了。记录所有藏宝点的最大值。importjava.io.PrintWriter;importjava.util.ArrayList;importjava.util.LinkedList;importjava.util.List;importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){intnsc.nextInt();ArrayListInteger[]mpnewArrayList[n];// 存储有向图for(inti0;in;i)mp[i]newArrayList();int[]dnewint[n];// 存储到当前节点的安全系数for(inti1;in;i){intjsc.nextInt();d[i]sc.nextInt();mp[j].add(i);// 添加一条从 j 到 i 的有向边}int[]mnnewint[n];// 记录从0到当前节点的最小安全系数mn[0]0x3f3f3f3f;// 默认为正无穷大ListIntegeransnewArrayList();// 存储藏宝地intmx0;// 存储所有小路安全系数的最小值最大LinkedListIntegerqnewLinkedList();q.add(0);// 添加起始点0while(!q.isEmpty()){intuq.poll();if(mp[u].isEmpty())// 如果当前节点没有子节点了则说明当前节点是一个藏宝地{ans.add(u);// 添加藏宝地mxMath.max(mx,mn[u]);// 获取所有小路安全系数的最小值最大}for(inti:mp[u])// 遍历当前节点的子节点{mn[i]Math.min(d[i],mn[u]);// 获取到当前节点的最小安全系数q.add(i);// 添加子节点}}out.println(mx);intpos0;for(inti:ans){if(mn[i]mx){if(pos!0)out.print( );out.print(i);}}out.flush();out.close();}staticScannerscnewScanner(System.in);staticPrintWriteroutnewPrintWriter(System.out);}ArrayListArrayListLinkedListarraylist和linkedlist的区别arraylist和linkedlist的区别bfsbfs如果有说错的 或者 不懂的 尽管提 嘻嘻一起进步闪现天梯赛