arbitrage.java

PKU中一些数据结构基本算法题的java实现

package PKU.FLOYD;
import java.util.*;


/**
 * ID:2240
 * Floyd算法
 * @author yhm
 *
 */
public class Arbitrage {

	static int size;
	static double[][] M;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseID = 1;
		while(cin.hasNext()){
			size = cin.nextInt();
			if(size==0) break;
			M = new double[size][size];
			Map<String, Integer> map = new HashMap<String, Integer>();
			for(int i=0;i<size;i++){
				String key = cin.next();
				map.put(key, i);
			}
			int m = cin.nextInt();
			for(int i=0;i<m;i++){
				int row = map.get(cin.next());
				double rate = cin.nextDouble();
				int col = map.get(cin.next());
				M[row][col] = rate;
			}
			
			System.out.print("Case "+caseID+": ");
			floyd();
			caseID++;
			
		}

	}
	static void floyd(){
		for(int m=0;m<size;m++){
			for(int row=0;row<size;row++){
				for(int col=0;col<size;col++){
					if(M[row][m]!=0 && M[m][col]!=0 && M[row][m]*M[m][col]>M[row][col]){
						M[row][col] = M[row][m]*M[m][col];
					}
				}
			}
		}
		
		boolean can = false;
		for(int i=0;i<size;i++){
			if(M[i][i]>1){
				can = true;
				break;
			}
		}
		
		if(can){
			System.out.println("Yes");
		}
		else{
			System.out.println("No");
		}
		
	}

}