当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

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

发表于: 2013-01-18   作者:128kj   来源:转载   浏览:
摘要: POJ 2197题意:   给定n个城市及其之间的距离,以及距离限制len 初始点s, 结束点e, 要求求出从s到e的所有不大于len的路径并输出,按照距离从小到大输出,如果距离相等, 就按照路径的字典升序输出。 样例: Sample Input 4 5        4个顶点,5条边 1 2 2
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;
      }
   }
}


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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 import java.util.*; public class Graph
//邻接表实现图的广搜和深搜(java模板) import java.util.*; public class GraphSearch{ private in
最近为了保研在复习数据结构和算法,想来可以用博客记录一些,以后或许能用的上。 首先说一下图的定
Author:Echo Chen(陈斌) Email:chenb19870707@gmail.com Blog:Blog.csdn.net/chen19870707 Dat
Author:Echo Chen(陈斌) Email:chenb19870707@gmail.com Blog:Blog.csdn.net/chen19870707 Dat
#include <iostream> #include <stdio.h> #include <cstdlib> #include <cstr
#include <iostream> #include <string> #include <queue> using namespace std;
关于树状数组:参看: http://128kj.iteye.com/blog/1743633 POJ3321 题意: 一棵具有n个节点的树,
Problem Description   多多终于从小学升入了初中。新班级共有n人,学号分别为从1~n。其中多多的
图的深搜与广搜 马上又要秋招了,赶紧复习下基础知识。这里复习下二叉树、图的深搜与广搜。从图的遍
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号