吝啬的国度--无向图,广度优先遍历,内存爆掉了

2024-04-23 14:32

本文主要是介绍吝啬的国度--无向图,广度优先遍历,内存爆掉了,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

地址:http://acm.nyist.net/JudgeOnline/problem.php?pid=20

吝啬的国度

时间限制: 1000 ms  |  内存限制: 65535 KB
难度: 3
描述
在一个吝啬的国度里有N个城市,这N个城市间只有N-1条路把这个N个城市连接起来。现在,Tom在第S号城市,他有张该国地图,他想知道如果自己要去参观第T号城市,必须经过的前一个城市是几号城市(假设你不走重复的路)。
输入
第一行输入一个整数M表示测试数据共有M(1<=M<=5)组
每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000),N表示城市的总个数,S表示参观者所在城市的编号
随后的N-1行,每行有两个正整数a,b(1<=a,b<=N),表示第a号城市和第b号城市之间有一条路连通。
输出
每组测试数据输N个正整数,其中,第i个数表示从S走到i号城市,必须要经过的上一个城市的编号。(其中i=S时,请输出-1)
样例输入
1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7
样例输出
-1 1 10 10 9 8 3 1 1 8

思路:不多说,~_~表示不知道题目说什么,不过当复习下知识点:向图,广度优先遍历吧。


附上自己的代码:居然超过了内存限制。。。苦逼~~~~,有时间再研究下,怎么优化

import java.util.ArrayList;
import java.util.Scanner;public class Main{public static void main(String[] args){Main main =new Main();main.solution();}public void solution(){Scanner cin=new Scanner(System.in);int n=cin.nextInt();while(n-->0){int allCity=cin.nextInt();int startCity=cin.nextInt();int [][] path=new int[allCity][allCity];for(int i=0;i<allCity-1;i++){	//是allCity-1条路,n座城市有n-1条路 --初始化数组,无向图int xi=cin.nextInt()-1;int xj=cin.nextInt()-1;path[xi][xj]=1;path[xj][xi]=1;}/*for(int[] a:path){for(int b:a)System.out.print(b);System.out.println();}*/ArrayList<Integer> queue=new ArrayList<Integer>();queue.add(startCity-1);while(queue.size()>0){	int tmp=queue.remove(0);for(int i=0;i<allCity;i++){	//进行广度优先遍历,由无向变成有向,即:将无根树变成有根树if(path[tmp][i]!=0){path[i][tmp]=0;queue.add(i);}}}for(int i=0;i<allCity;i++){		//寻找路径if(i==startCity-1)System.out.print("-1 ");else{for(int j=0;j<allCity;j++){if(path[j][i]!=0){System.out.print(j+1+" ");break;}}}}System.out.println();}}
}

最后附上java能ac的代码: http://blog.csdn.net/taotaotaotao910429/article/details/7850829 可以参考下。。不明白,模拟一遍就差不多了,感觉最直接的方法就是模拟一下,就知道整体式怎么一回事了

7.29号,今天对着能ac的代码又做了一遍,发现思路跟昨天是一样的,关键是怎么优化,将二维数组变为一维数组。用上强大的集合。。不过也是勉强的通过。

代码如下:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class result
{ArrayList<Integer>vector=new ArrayList<Integer>();
}
public class Main {static result results[];static int path[],start,citynumber;static boolean mark[];public static void bfs(){Queue<Integer>queue=new LinkedList<Integer>();queue.add(start);mark[start]=true;while(!queue.isEmpty()){int s=queue.remove();for(int i=0;i<results[s].vector.size();i++){if(!mark[results[s].vector.get(i)]){path[results[s].vector.get(i)]=s;mark[results[s].vector.get(i)]=true;queue.add(results[s].vector.get(i));}}}}public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int cases=scanner.nextInt();while(cases--!=0){citynumber=scanner.nextInt();start=scanner.nextInt();results=new result[citynumber+1];path=new int[citynumber+1];mark=new boolean[citynumber+1];Arrays.fill(path, -1);	//全部初始化为-1for(int i=0;i<=citynumber;i++){results[i]=new result();}for(int i=0;i<citynumber-1;i++){int x,y;x=scanner.nextInt();y=scanner.nextInt();results[x].vector.add(y);results[y].vector.add(x);}bfs();for(int i=1;i<=citynumber;i++){System.out.print(path[i]+" ");}}}
}



这篇关于吝啬的国度--无向图,广度优先遍历,内存爆掉了的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/929060

相关文章

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Golang基于内存的键值存储缓存库go-cache

《Golang基于内存的键值存储缓存库go-cache》go-cache是一个内存中的key:valuestore/cache库,适用于单机应用程序,本文主要介绍了Golang基于内存的键值存储缓存库... 目录文档安装方法示例1示例2使用注意点优点缺点go-cache 和 Redis 缓存对比1)功能特性

Go使用pprof进行CPU,内存和阻塞情况分析

《Go使用pprof进行CPU,内存和阻塞情况分析》Go语言提供了强大的pprof工具,用于分析CPU、内存、Goroutine阻塞等性能问题,帮助开发者优化程序,提高运行效率,下面我们就来深入了解下... 目录1. pprof 介绍2. 快速上手:启用 pprof3. CPU Profiling:分析 C

golang内存对齐的项目实践

《golang内存对齐的项目实践》本文主要介绍了golang内存对齐的项目实践,内存对齐不仅有助于提高内存访问效率,还确保了与硬件接口的兼容性,是Go语言编程中不可忽视的重要优化手段,下面就来介绍一下... 目录一、结构体中的字段顺序与内存对齐二、内存对齐的原理与规则三、调整结构体字段顺序优化内存对齐四、内

Linux内存泄露的原因排查和解决方案(内存管理方法)

《Linux内存泄露的原因排查和解决方案(内存管理方法)》文章主要介绍了运维团队在Linux处理LB服务内存暴涨、内存报警问题的过程,从发现问题、排查原因到制定解决方案,并从中学习了Linux内存管理... 目录一、问题二、排查过程三、解决方案四、内存管理方法1)linux内存寻址2)Linux分页机制3)

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(

Java循环创建对象内存溢出的解决方法

《Java循环创建对象内存溢出的解决方法》在Java中,如果在循环中不当地创建大量对象而不及时释放内存,很容易导致内存溢出(OutOfMemoryError),所以本文给大家介绍了Java循环创建对象... 目录问题1. 解决方案2. 示例代码2.1 原始版本(可能导致内存溢出)2.2 修改后的版本问题在

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Redis多种内存淘汰策略及配置技巧分享

《Redis多种内存淘汰策略及配置技巧分享》本文介绍了Redis内存满时的淘汰机制,包括内存淘汰机制的概念,Redis提供的8种淘汰策略(如noeviction、volatile-lru等)及其适用场... 目录前言一、什么是 Redis 的内存淘汰机制?二、Redis 内存淘汰策略1. pythonnoe

Java内存泄漏问题的排查、优化与最佳实践

《Java内存泄漏问题的排查、优化与最佳实践》在Java开发中,内存泄漏是一个常见且令人头疼的问题,内存泄漏指的是程序在运行过程中,已经不再使用的对象没有被及时释放,从而导致内存占用不断增加,最终... 目录引言1. 什么是内存泄漏?常见的内存泄漏情况2. 如何排查 Java 中的内存泄漏?2.1 使用 J