3629303_ac_375ms_3024k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;
import java.math.*;

public class Main {
	private Scanner in;
	private TreeMap <String, Integer> tm;
	private int cnt;
	private LinkedList[] ll = new LinkedList[60];
	private Rate[][] rate = new Rate[60][60];
	private String[] name = new String[60];

	class Rate {
		BigInteger a, b;

		public Rate(BigInteger a, BigInteger b) {
			this.a = a;
			this.b = b;
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}

	private void run() {
		in = new Scanner(System.in);
		String command;
		String left, right;
		BigInteger a, b;
		int ida, idb;

		tm = new TreeMap <String, Integer> ();
		cnt = 0;
		for (int i = 0; i < 60; i++) {
			ll[i] = new LinkedList<Integer> ();
			Arrays.fill(rate[i], null);
		}
		while (true) {
			command = in.next();
			if (".".equals(command)) {
				break;
			}
			if ("!".equals(command)) {
				a = in.nextBigInteger();
				left = in.next();
				in.next();
				b = in.nextBigInteger();
				right = in.next();
				ida = insert(left);
				idb = insert(right);
				ll[ida].add(idb);
				rate[ida][idb] = new Rate(a, b);
				ll[idb].add(ida);
				rate[idb][ida] = new Rate(b, a);
				continue;
			}
			left = in.next();
			in.next();
			right = in.next();
			solve(tm.get(left), tm.get(right));
		}
	}

	private void solve(int ida, int idb) {
		int[] queue = new int[100];
		int[] prev = new int[100];
		int front, rear;
		boolean[] visited = new boolean[100];

		prev[0] = -1;
		queue[0] = ida;
		front = 0;
		rear = 1;
		visited[ida] = true;
label:	while (front != rear) {
			int id = queue[front++];

			for (int i = 0; i < ll[id].size(); i++) {
				int aid = (Integer)ll[id].get(i);
				if (visited[aid] == true) {
					continue;
				}
				visited[aid] = true;
				queue[rear++] = aid;
				prev[aid] = id;
				if (aid == idb) {
					break label;
				}
			}
		}
		if (visited[idb] == false) {
			System.out.println("? " + name[ida] + " = ? " + name[idb]);
			return ;
		}
		LinkedList<BigInteger> ratearray = new LinkedList<BigInteger> ();
		BigInteger ansa, ansb;
		int tmp = idb;
		while (true) {
			ratearray.addFirst(rate[prev[tmp]][tmp].b);
			ratearray.addFirst(rate[prev[tmp]][tmp].a);
			tmp = prev[tmp];
			if (tmp == ida) {
				break;
			}
		}
		while (ratearray.size() != 2) {
			BigInteger a, b, c, d, e;
			a = ratearray.get(0);
			b = ratearray.get(1);
			c = ratearray.get(2);
			d = ratearray.get(3);
			for (int i = 0; i < 4; i++) {
				ratearray.removeFirst();
			}
			e = lcm(b, c);
			a = a.multiply(e.divide(b));
			d = d.multiply(e.divide(c));
			ratearray.addFirst(d);
			ratearray.addFirst(a);
		}
		ansa = ratearray.get(0);
		ansb = ratearray.get(1);
		BigInteger gcd = ansa.gcd(ansb);
		ansa = ansa.divide(gcd);
		ansb = ansb.divide(gcd);
		System.out.println(ansa + " " + name[ida] + " = " + ansb + " " + name[idb]);
	}

	private BigInteger lcm(BigInteger a, BigInteger b) {
		return a.multiply(b).divide(a.gcd(b));
	}

	private int insert(String str) {
		if (tm.containsKey(str)) {
			return tm.get(str);
		}
		tm.put(str, cnt);
		name[cnt] = str;
		return cnt++;
	}
}