首页 > 专题系列 > Java解POJ > POJ 2570 Fiber Network [解题报告] Java
2013
11-11

POJ 2570 Fiber Network [解题报告] Java

Fiber Network

问题描述 :

Several startup companies have decided to build a better Internet, called the “FiberNet”. They have already installed many nodes that act as routers all around the world. Unfortunately, they started to quarrel about the connecting lines, and ended up with every company laying its own set of cables between some of the nodes.

Now, service providers, who want to send data from node A to node B are curious, which company is able to provide the necessary connections. Help the providers by answering their queries.

输入:

The input contains several test cases. Each test case starts with the number of nodes of the network n. Input is terminated by n=0. Otherwise, 1<=n<=200. Nodes have the numbers 1, ..., n. Then follows a list of connections. Every connection starts with two numbers A, B. The list of connections is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the unidirectional connection, respectively. For every connection, the two nodes are followed by the companies that have a connection from node A to node B. A company is identified by a lower-case letter. The set of companies having a connection is just a word composed of lower-case letters.

After the list of connections, each test case is completed by a list of queries. Each query consists of two numbers A, B. The list (and with it the test case) is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the query. You may assume that no connection and no query contains identical start and end nodes.

输出:

For each query in every test case generate a line containing the identifiers of all the companies, that can route data packages on their own connections from the start node to the end node of the query. If there are no companies, output “-” instead. Output a blank line after each test case.

样例输入:

3
1 2 abc
2 3 ad
1 3 b
3 1 de
0 0
1 3
2 1
3 2
0 0
2
1 2 z
0 0
1 2
2 1
0 0
0

样例输出:

ab
d
-

z
-

解题代码:

//* @author: [email protected]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main
{
 static int[][] m=new int[201][201];
 public static void main(String[] args) throws NumberFormatException, IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  while(true)
   {
    int n=Integer.parseInt(in.readLine());
    if(n==0)break;
    for(int i=0;i< 201;i++)
     for(int j=0;j< 201;j++)
	m[i][j]=0;
    String[] ss;
    while(true)
    {
	ss=in.readLine().split(" ");
	int a=Integer.parseInt(ss[0]);
	int b=Integer.parseInt(ss[1]);
	if(a==0&&b==0)break;
	for(int i=0;i< ss[2].length();i++)
	{
	  int w=ss[2].charAt(i)-'a';
	  m[a][b]|=1<< w;
	}
     }
     for(int k=1;k<=n;k++)
       for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	   m[i][j]|=m[i][k]&m[k][j];
     while(true)
     {
	ss=in.readLine().split(" ");
	int a=Integer.parseInt(ss[0]);
	int b=Integer.parseInt(ss[1]);
	if(a==0&&b==0) break;
	char ch;
	for(ch='a';ch<='z';ch++)
	{
	  if((m[a][b]&(1<<(ch-'a')))!=0)
	   System.out.print(ch);
	}
	if(m[a][b]==0) System.out.print("-");
	System.out.println();
      }
     System.out.println();
   }
 }
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。