- 浏览: 583571 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
POJ 2197题意:
给定n个城市及其之间的距离,以及距离限制len 初始点s, 结束点e,
要求求出从s到e的所有不大于len的路径并输出,按照距离从小到大输出,如果距离相等,
就按照路径的字典升序输出。
样例:
Sample Input
4 5 4个顶点,5条边
1 2 2 顶点1到2之间的距离为2
1 3 3
1 4 1
2 3 2
3 4 4
1 3 //起点和终点
4 //距离限制
-1
Sample Output
Case 1:
3: 1 3
4: 1 2 3
思路:明显DFS+记录路径。
给定n个城市及其之间的距离,以及距离限制len 初始点s, 结束点e,
要求求出从s到e的所有不大于len的路径并输出,按照距离从小到大输出,如果距离相等,
就按照路径的字典升序输出。
样例:
Sample Input
4 5 4个顶点,5条边
1 2 2 顶点1到2之间的距离为2
1 3 3
1 4 1
2 3 2
3 4 4
1 3 //起点和终点
4 //距离限制
-1
Sample Output
Case 1:
3: 1 3
4: 1 2 3
思路:明显DFS+记录路径。
import java.util.*; public class Main{ static final int INF=100000; Point arr[];//记录符合条件所有解(终点) int v,s,e,len;//顶点数,起点,终点,距离限定 int map[][];//城市的邻接矩阵 boolean f[];//深搜时记录顶点是否访问过 int x[];//用于记录从起点到终点的路径 int ii;//arr[]的下标,从0开始符合条件 static int counter = 0; public Main(int v,int s,int e,int len,int[][] map){ this.v=v;//顶点数 this.s=s;//起点 this.e=e;//终点 this.len=len;//距离限定 this.map=map;//图的邻接矩阵 f =new boolean[v+1]; x=new int[v+1]; arr=new Point[4000]; for(int i=0;i<4000;i++) arr[i]=new Point(); } public static void main(String[] args){ Scanner in=new Scanner(System.in); int v, r,s, e,len;//r:边的数目 int[][] map; while(true) { v=in.nextInt(); if(v==-1) break; r=in.nextInt(); map=new int[v+1][v+1];//邻接矩阵 for(int i=1;i<=v;i++) { for(int j=1;j<=v;j++) { map[i][j] = INF; } } for(int i=0;i<r;i++) { int a,b,c; a=in.nextInt(); b=in.nextInt(); c=in.nextInt(); map[a][b] = map[b][a] = c;//这是无向图 } s=in.nextInt(); e=in.nextInt(); len=in.nextInt(); Main m=new Main(v,s,e,len,map); m.go(); } } public void go(){ System.out. printf("Case %d:\n",++counter); f[s] = true; x[0] = s;//旅游的步骤,从0(起点)开始 ii = 0; dfs(s,0,1);//旅游的步骤,第1步 if(ii==0) System.out.printf(" NO ACCEPTABLE TOURS\n"); else { Arrays.sort(arr ,0, ii ,new SampleComparator()); for(int i=0;i<ii;i++) { System.out.printf(" %d: ",arr[i].sum); for(int j=0;j<arr[i].jj;j++) { System.out.printf("%d ",arr[i].num[j]); } System.out.println(); } } System.out.println(); } //ind:旅游的步骤,从0(起点)开始, //sum:旅游的距离 //cur:旅游的当前点 void dfs(int cur , int sum , int ind){ if( sum > len ) return ; if( cur == e){//到达终点 arr[ii].sum = sum;//记录起点到终点的距离 for(int i=0;i<ind;i++)//记当起点到终点的路径 { arr[ii].num[i] = x[i]; } arr[ii++].jj = ind;//记录起点到终点经过的城市数 return ; } for(int i=1;i<=v;i++)//搜索当前点的所有邻接点 { if( !f[i] && map[cur][i] < INF )//i没有访问过,且有路径可通。 { if( sum + map[cur][i] <= len )//剪枝 { f[i] = true; x[ind++] = i;//记录路径 dfs(i , sum+map[cur][i],ind);//递归深搜 f[i] = false;//回溯 x[ind--] = 0;//回溯 } } } } } class Point{ int jj;//从起点到此点经过的城市数目 int sum ;//从起点到此点的距离 int num[]=new int[25];//从起点到此点的路径 } class SampleComparator implements Comparator<Point> { public int compare(Point a, Point b) { if( a.sum != b.sum ){ if(a.sum < b.sum) return -1; else return 1; } else{ int len1 = a.jj; int len2 = b.jj; for(int i=0;i<Math.max(a.jj,b.jj);i++) { if( a.num[i] != b.num[i] ) { if(a.num[i] < b.num[i]) return -1; else return 1; } } return 0; } } }
- Main2197.zip (1.5 KB)
- 下载次数: 2
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3656题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2979POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1430POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
图的练习题(有解答)
2012-12-27 22:23 26111. 填空题 ⑴ 设无向图G ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1847题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1593关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1821关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1807POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1829POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1724POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1562分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2173接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1499关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1352接前文:二维树状数组学习之一:彻底理解http://128kj ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2404//邻接表实现图的广搜和深搜(java模板) impor ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1765关于树状数组:参看:http://128kj.iteye.co ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1838经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1667关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1745关于树状数组,请参考:http://128kj.iteye.c ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2021POJ2299题意: 给出长度为n的序列,每次只能交换 ...
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1745671
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1750462
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1752661
NULL 博文链接:https://128kj.iteye.com/blog/1754177
NULL 博文链接:https://128kj.iteye.com/blog/1753387
NULL 博文链接:https://128kj.iteye.com/blog/1749213
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1759266
NULL 博文链接:https://128kj.iteye.com/blog/1754170
NULL 博文链接:https://128kj.iteye.com/blog/1757060
博客链接 http://blog.csdn.net/CABI_ZGX/article/details/52701138
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
POJ1523-SPF 【割点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/84AS1D
C + + language learning poj100 question bank and code
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
很详尽的讲述了简单的深搜,宽搜算法,另外还有剪枝策略,另外附加了poj上的题目举例分析。 (作者:东北师大计算机学院程文华)