首页 > 专题系列 > Java解POJ > POJ 3893 Hard-working Student [解题报告] Java
2013
11-13

POJ 3893 Hard-working Student [解题报告] Java

Hard-working Student

问题描述 :

Billy is a hard-working student. He is fond of computers and intends to learn as much as possible. Now he studies graph theory, and must write a program to build the graph which is shown on the Figure.

The vertices of the graph are labeled sequentially with integer keys starting from 0 to N – 1 (N≤10000). There are two types of edges: backward edges – labeled with B in the Figure (for example from node 4 to node 2, or from node 3 to node 1), and forward edges, labeled with F in the Figure (for example from node 1 to node 2 or from node 0 to node 3). Billy’s program starts with an initial graph that contains the vertices 0, 1, 2, 3, and must continue to build the graph based on a sequence of commands written in a text file. A command has the following specification:

index0 string_of_characters index1

where index0 and index1 are the keys of vertices, and string_of_characters is a sequence of actions executed from right to left. An action is represented by one of the following characters:



Character Action
f Follow the Forward edge if it does exist or creates it and the corresponding vertex from an argument node
b Follow the backward edge if it does exist or creates it and corresponding vertex, starting from an argument node
k Prints the key of the argument node
< v[index0] = argument node
= Prints ‘=’ if v[index0] == node or ‘#’ otherwise



where v is the array of the nodes of the graph. The argument of the first operation is the node v[index1]. The result of the operations f and b is a node that represents the argument for all the other operations. The operations < and = are the leftmost specified. For example, for the command 4 <kff 0 the actions are:


index0 = 4, index1 = 0

x = f(v[0]) // forward to node 3, x = 3

y = f(x) // forward creates node (4), y = 4

k(y) // prints the key (4)

V[4] = y // put node (4) in array v

A node is put in the array v only by the command <. Initially the array contains the nodes with keys 0, 1, 2, 3, v[0]=0, v[1]=1,v[2]=2 and v[3]=3.

输入:

The file contains the sequence of commands. White spaces can occur freely in the input. The input data terminate with an end of file.

输出:

Each print must be to the standard output from the beginning of a line. There are no empty lines in between.

样例输入:

4 <kf 3
0 =bb 4
7 <ff 3

样例输出:

4
=

解题代码:

//* @author:
import java.util.*;
public class Main{
  public static void main(String args[]){
   Scanner in=new Scanner(System.in);
   char s[]=new char[10001];
   int v[]=new int[10001];
   v[1]=1;v[2]=2;v[3]=3;
   int a,b,len;
   while(in.hasNext()){
    a=in.nextInt();
    s=in.next().toCharArray();
    b=in.nextInt();
    b=v[b];
    len=s.length;
    for(int i=len-1; i>=0; i--){
     if(s[i]=='< ')
      v[a]=b;
     if(s[i]=='=')
      System.out.println(v[a]==b?"=":"#");
     if(s[i]=='k')
      System.out.printf("%d\n",b);
     if(s[i]=='b')
       b-=2;
     if(s[i]=='f'){
       if((b&1)!=0)
         b++;
       else
         b+=3;
     }
     }
    }
  }
}

  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯