Problem C: Exchange Rates

Using money to pay for goods and services usually makes life easier, but sometimes people prefer to trade items directly without any money changing hands. In order to ensure a consistent "price", traders set an exchange rate between items. The exchange rate between two items A and B is expressed as two positive integers m and n, and says that m of item A is worth n of item B. For example, 2 stoves might be worth 3 refrigerators. (Mathematically, 1 stove is worth 1.5 refrigerators, but since it's hard to find half a refrigerator, exchange rates are always expressed using integers.)

Your job is to write a program that, given a list of exchange rates, calculates the exchange rate between any two items.

The input file contains one or more commands, followed by a line beginning with a period that signals the end of the file. Each command is on a line by itself and is either an assertion or a query. An assertion begins with an exclamation point and has the format

! m itema = n itemb

? itema = itemb

Note:

• Item names will have length at most 20 and will contain only lowercase letters.
• Only the singular form of an item name will be used (no plurals).
• There will be at most 60 distinct items.
• There will be at most one assertion for any pair of distinct items.
• There will be no contradictory assertions. For example, "2 pig = 1 cow", "2 cow = 1 horse", and "2 horse = 3 pig" are contradictory.
• Assertions are not necessarily in lowest terms, but output must be.
• Although assertions use numbers less than 100, queries may result in larger numbers that will not exceed 10000 when reduced to lowest terms.

Example input:

! 6 shirt = 15 sock
! 47 underwear = 9 pant
? sock = shirt
? shirt = pant
! 2 sock = 1 underwear
? pant = shirt
.

Example output:

5 sock = 2 shirt
? shirt = ? pant
45 pant = 188 shirt

---

中間用了 floyd 算法。

import java.util.Scanner;
import java.util.HashMap;
import java.math.BigInteger;

class Main {
	public static void main(String args[]) {
		Scanner cin = new Scanner(System.in);
		String cmd, A, B;
		HashMap<String, Integer> item = new HashMap<String, Integer>();
		BigInteger[][] GA = new BigInteger[100][100];
		BigInteger[][] GB = new BigInteger[100][100];
		int i, j, k, size = 0, ix, iy;
		for(i = 0; i < 100; i++) {
			for(j = 0; j < 100; j++) {
				GA[i][j] = BigInteger.ZERO;
				GB[i][j] = BigInteger.ZERO;
			}
		}
		while(cin.hasNext()) {
			cmd = cin.next();
			if(cmd.equals("."))	
				break;
			if(cmd.equals("!")) {
				int x, y;
				x = cin.nextInt();
				A = cin.next();
				if(item.get(A) == null) {
					++size;
					item.put(A, size);
					ix = size;
				} else	ix = item.get(A);
				cin.next();
				y = cin.nextInt();
				B = cin.next();
				if(item.get(B) == null) {
					++size;
					item.put(B, size);
					iy = size;
				} else	iy = item.get(B);
				GA[ix][iy] = BigInteger.valueOf(x);
				GB[ix][iy] = BigInteger.valueOf(y);
				GA[iy][ix] = BigInteger.valueOf(y);
				GB[iy][ix] = BigInteger.valueOf(x);
			} else {
				for(k = 1; k <= size; k++) {
					for(i = 1; i <= size; i++) {
						for(j = 1; j <= size; j++) {
							if(GA[i][k].equals(BigInteger.ZERO))
								continue;
							if(GA[k][j].equals(BigInteger.ZERO))
								continue;
							GA[i][j] = GA[i][k].multiply(GA[k][j]);
							GB[i][j] = GB[i][k].multiply(GB[k][j]);
							BigInteger g = GA[i][j].gcd(GB[i][j]);
							GA[i][j] = GA[i][j].divide(g);
							GB[i][j] = GB[i][j].divide(g);
						}						
					}
				} 
				A = cin.next();
				cin.next();
				B = cin.next();
				if(item.get(A) == null) {
					++size;
					item.put(A, size);
					ix = size;
				} else	ix = item.get(A);
				if(item.get(B) == null) {
					++size;
					item.put(B, size);
					iy = size;
				} else	iy = item.get(B);
				if(GA[ix][iy].equals(BigInteger.ZERO))
					System.out.println("? " + A + " = ? " + B);
				else
					System.out.println(GA[ix][iy] + " " + A + " = " + GB[ix][iy] + " " + B);
			}
		}
	}
}
/* 
! 6 shirt = 15 sock
! 47 underwear = 9 pant
? sock = shirt
? shirt = pant
! 2 sock = 1 underwear
? pant = shirt
.
*/