图的深搜+回溯练习题：POJ2197_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+记录路径。

class="java">
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