首页 > 专题系列 > Java解POJ > POJ 1125 Stockbroker Grapevine [解题报告] Java
2013
11-09

POJ 1125 Stockbroker Grapevine [解题报告] Java

Stockbroker Grapevine

问题描述 :

Stockbrokers are known to overreact to rumours. You have been contracted to develop a method of spreading disinformation amongst the stockbrokers to give your employer the tactical edge in the stock market. For maximum effect, you have to spread the rumours in the fastest possible way.

Unfortunately for you, stockbrokers only trust information coming from their “Trusted sources” This means you have to take into account the structure of their contacts when starting a rumour. It takes a certain amount of time for a specific stockbroker to pass the rumour on to each of his colleagues. Your task will be to write a program that tells you which stockbroker to choose as your starting point for the rumour, as well as the time it will take for the rumour to spread throughout the stockbroker community. This duration is measured as the time needed for the last person to receive the information.

输入:

Your program will input data for different sets of stockbrokers. Each set starts with a line with the number of stockbrokers. Following this is a line for each stockbroker which contains the number of people who they have contact with, who these people are, and the time taken for them to pass the message to each person. The format of each stockbroker line is as follows: The line starts with the number of contacts (n), followed by n pairs of integers, one pair for each contact. Each pair lists first a number referring to the contact (e.g. a ’1′ means person number one in the set), followed by the time in minutes taken to pass a message to that person. There are no special punctuation symbols or spacing rules.

Each person is numbered 1 through to the number of stockbrokers. The time taken to pass the message on will be between 1 and 10 minutes (inclusive), and the number of contacts will range between 0 and one less than the number of stockbrokers. The number of stockbrokers will range from 1 to 100. The input is terminated by a set of stockbrokers containing 0 (zero) people.

输出:

For each set of data, your program must output a single line containing the person who results in the fastest message transmission, and how long before the last person will receive any given message after you give it to this person, measured in integer minutes.

It is possible that your program will receive a network of connections that excludes some persons, i.e. some people may be unreachable. If your program detects such a broken network, simply output the message “disjoint”. Note that the time taken to pass the message from person A to person B is not necessarily the same as the time taken to pass it from B to A, if such transmission is possible at all.

样例输入:

3
2 2 4 3 5
2 1 2 3 6
2 1 2 2 2
5
3 4 4 2 8 5 3
1 5 8
4 1 6 4 10 2 7 5 2
0
2 2 5 1 5
0

样例输出:

3 2
3 10

解题代码:

(1)
import java.io.BufferedInputStream;   
import java.util.Scanner;   
  
  
/*  
 * To change this template, choose Tools | Templates  
 * and open the template in the editor.  
 */  
/**  
 * 求最短路径  
 * 有两种方法。用弗洛德相对简单点  
 * 这道题理解题意后就不难了。代码的编写也比较容易。  
 * 只是初始化和单个顶点的环注意下就行了  
 * poj1125  
 * @author NC  
 */  
public class Main {   
  
    final static int disjoint = 1000;//最多100个人,每个人最多花费10分钟   
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        while (scan.hasNext()) {   
            int n = scan.nextInt();   
            if (n == 0) {   
                break;   
            }   
            //初始化矩阵,默认不可达,stockbroker的编号是从1开始的   
            int[][] times = new int[n + 1][n + 1];   
            for (int i = 0; i < n + 1; i++) {   
                for (int j = 0; j < n + 1; j++) {   
                    times[i][j] = disjoint;   
                }   
            }   
            for (int i = 1; i <= n; i++) {   
                int stockbroker = i;   
                int number = scan.nextInt();   
                for (int j = 1; j <= number; j++) {   
                    int contact = scan.nextInt();   
                    int time = scan.nextInt();   
                    times[stockbroker][contact] = time;   
                }   
            }   
            //弗洛依德算法,顶点i到j经过k点   
            for (int k = 1; k <= n; k++) {   
                for (int i = 1; i <= n; i++) {   
                    for (int j = 1; j <= n; j++) {   
                        if (i != j && times[i][k] + times[k][j] < times[i][j]) {   
                            times[i][j] = times[i][k] + times[k][j];   
                        }   
                    }   
                }   
            }   
            //注意,单个顶点本身不应该有环,这里是无穷大   
            //求每个经纪人将信息传递给所有人知道所要花费的时间,存储在第0列   
            for (int i = 1; i <= n; i++) {   
                times[i][0] = 0;//赋0方便比较大小   
                for (int j = 1; j <= n; j++) {   
                    if (times[i][j] > times[i][0] && i != j) {//求max   
                        times[i][0] = times[i][j];   
                    }   
                }   
            }   
            //找出最小耗时,存在第0行第0列   
            int index = 0;   
            for (int i = 1; i <= n; i++) {   
                if (times[i][0] < times[0][0] && times[i][0] != disjoint) {//求min   
                    times[0][0] = times[i][0];   
                    index = i;   
                }   
            }   
            //输出结果   
            if (index == 0) {   
                System.out.println("disjoint");   
            } else {   
                System.out.println(index + " " + times[0][0]);   
            }   
        }   
    }   
}  
(2)
import java.io.BufferedInputStream; 
import java.io.IOException; 
import java.util.Scanner; 

public class Main { 

    final static int MAXVALUE = 10000000; 

    public static void main(String[] args) throws NumberFormatException, 
            IOException { 
        Scanner read = new Scanner(new BufferedInputStream(System.in)); 
        int t, num; 
        int[][] p; 
        int min, max, start; 
        while ((t = read.nextInt()) != 0) { 
            p = new int[t][t]; 
            for (int i = 0; i < t; i++) { 
                for (int j = 0; j < t; j++) { 
                    p[i][j] = MAXVALUE; 
                } 
            } 
            for (int i = 0; i < t; i++) { 
                p[i][i] = 0; 
            } 
            for (int i = 0; i < t; i++) { 
                num = read.nextInt(); 
                for (int j = 0; j < num; j++) { 
                    p[i][read.nextInt() - 1] = read.nextInt(); 
                } 
            } 
            for (int k = 0; k < t; k++) { 
                for (int i = 0; i < t; i++) { 
                    for (int j = 0; j < t; j++) { 
                        if (p[i][j] > p[i][k] + p[k][j]) { 
                            p[i][j] = p[i][k] + p[k][j]; 
                        } 
                    } 
                } 
            } 
            min = Integer.MAX_VALUE; 
            start = -1; 
            loop: for (int i = 0; i < t; i++) { 
                max = Integer.MIN_VALUE; 
                for (int j = 0; j < t; j++) { 
                    if (p[i][j] == MAXVALUE) { 
                        continue loop; 
                    } else { 
                        max = Math.max(max, p[i][j]); 
                    } 
                } 
                if (max < min) { 
                    min = max; 
                    start = i; 
                } 
            } 
            if (start != -1) { 
                System.out.println((start + 1) + " " + min); 
            } else { 
                System.out.println("disjoint"); 
            } 
        } 
    } 
}

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.