`
128kj
  • 浏览: 603953 次
  • 来自: ...
社区版块
存档分类
最新评论

图的深搜+回溯练习题:POJ2197

阅读更多
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+记录路径。

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;
      }
   }
}


0
0
分享到:
评论

相关推荐

    图的深搜+树状数组练习 POJ 3321(JAVA)

    标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...

    深搜+宽搜+剪枝 配合POJ题目

    各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。

    ACM常用算法及其相应的练习题.docx

    本资源总结了 ACM 竞赛中常用的算法和相应的练习题,涵盖了基础算法、图算法、数据结构、搜索、动态规划和数学等方面的知识点。 一、基础算法 * 枚举:poj1753, poj2965 * 贪心:poj1328, poj2109, poj2586 * 递归...

    极角排序:POJ 1696(叉积+深搜)

    深度优先搜索(Deepth-First Search, DFS)则是一种图或树遍历的方法,常用于解决复杂结构的搜索问题,如迷宫求解、有向图的拓扑排序等。 结合标签“源码”和“工具”,我们可以推断这篇博客可能提供了解决POJ 1696...

    POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】

    3. **回溯法**:回溯法是一种试探性的解决问题的方法,当发现当前选择可能导致无法达到目标时,就退回一步,尝试其他的可能性。在Curling 2.0问题中,回溯法与DFS相结合,可以有效地在多叉树状结构中寻找解决方案,...

    ACM常用算法及其相应的练习题 (2).docx

    ACM常用算法及其相应的练习题 本资源摘要信息涵盖了ACM常用的算法和相应的练习题,旨在帮助程序员和算法爱好者快速学习和掌握这些算法。下面详细介绍这些算法和练习题。 一、基本算法 本部分涵盖了基本算法,包括...

    大(小)顶堆练习:POJ 1442

    标题 "大(小)顶堆练习:POJ 1442" 提示我们这是一个关于数据结构和算法的练习题目,特别关注大顶堆或小顶堆的应用。在计算机科学中,大顶堆和小顶堆是两种特殊的二叉堆,它们分别保证了根节点是其子树中最大或最小...

    树状数组练习:POJ 3067

    【标题】"树状数组练习:POJ 3067" 树状数组,也称为线段树(Segment Tree),是一种高效的数据结构,用于处理区间查询和修改问题。在这个问题中,我们通过分析POJ 3067的题目来探讨如何应用树状数组解决实际问题。...

    ACMer需要掌握的算法讲解 (2).docx

    * POJ3109、POJ1478、POJ1462、POJ2729、POJ2048、POJ3336、POJ3315、POJ2148、POJ1263 八、附录 * ACM算法列表 + 哈希表、哈希数组 + 堆、优先队列 + 双端队列可并堆左偏堆 + Treap伸展树并查集 + 集合计数...

    凸包练习: POJ 2187(JAVA)

    【标题】"凸包练习: POJ 2187(JAVA)" 是一个关于编程算法的挑战,主要涉及计算机科学中的几何算法。在本问题中,我们关注的是二维平面上的点集及其凸包(Convex Hull)的概念。凸包可以被理解为一个最小的多边形,该...

    ACM常用算法及其相应的练习题 (2).pdf

    "ACM常用算法及其相应的练习题" 《ACM常用算法及其相应的练习题》是一份涵盖了ACM常用算法的题目集,旨在帮助程序员和 ACM 竞赛选手掌握常用的算法和数据结构。下面是对该文件的详细解析: 一、基本算法 * 枚举...

    大顶堆应用:POJ2010

    标题“大顶堆应用:POJ2010”指的是一个关于大顶堆算法在解决实际问题中的应用,特别是针对编程竞赛网站POJ(Programming Online Judge)上的问题2010。大顶堆是一种特殊的完全二叉树,其每个节点的值都大于或等于其...

    树状数组练习:POJ 2481(JAVA)

    【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...

    ACM 题型

    - 示例题目:poj1191, poj1054, poj3280, poj2029, poj2948, poj1925, poj3034 2. **四边形不等式** - 示例题目:POJ3254, poj2411, poj1185 3. **记忆化搜索** - 示例题目:poj2057, poj1947, poj2486, poj...

    滚动数组应用:POJ 1159

    标题“滚动数组应用:POJ 1159”指的是一个关于编程竞赛问题的解决方案,该问题在POJ(Programming Online Judge)平台上被提出。滚动数组是一种优化动态规划算法的技术,通过巧妙地重用和更新已经计算过的状态,减少...

    田忌赛马: POJ 2287(贪心解法)

    POJ(Programming Online Judge)是国内外广受欢迎的在线编程评测系统,其中的2287题正是以"田忌赛马"为背景的算法问题,主要考察选手对贪心策略的理解和应用。 贪心算法是一种在每一步选择中都采取当前状态下最好...

    堆排序练习:POJ 2388

    标题“堆排序练习:POJ 2388”指的是一个关于使用堆排序算法解决编程竞赛问题的实践案例。在编程竞赛中,如POJ(Programming Online Judge)平台上的问题2388,参赛者经常需要高效地解决排序问题,而堆排序作为一种...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **例题**:poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 - **解释**:最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法以及堆优化的Dijkstra算法等。 ##### (3) 最小生成树算法 - **例题**...

    直接插入排序练习:POJ 2388

    这个练习题目,"POJ 2388",显然是通过编程实现直接插入排序来解决一个特定的问题。在这个问题中,我们需要理解直接插入排序的机制,并能用Java语言编写出高效的代码。 直接插入排序的基本步骤如下: 1. 从第二个...

Global site tag (gtag.js) - Google Analytics