首页 > 专题系列 > Java解POJ > POJ 2132 Cow Math [解题报告] Java
2013
11-10

POJ 2132 Cow Math [解题报告] Java

Cow Math

问题描述 :

Taking their cue from the builders of the USA’s Interstate Highway system, the cows have introduced the Interpasture Path numbering system. They have already numbered the N (2 <= N <= 25) pastures with the integers 1..N and now are numbering each path between two pastures with its own distinct Interpasture Path number in the range 1..2000

(e.g., I-9 and I-16).

In an example Interpasture Path map, four pastures numbered 1, 2, 3, and 4 are connected by Interpasture Paths I-3, I-6, I-9, and I-16:

                  4--< I-6>--2

/ /
< I-16> < I-9>
/ /
1--< I-3>--3

Bessie likes to walk from pasture 1 to pasture 2 on the nifty new Interpasture system. During each walk, she never visits the same pasture twice, so possible walks on the sample map above are 1-4-2 and 1-3-2.

Over the years, Bessie has developed an amazing mathematical skill that she likes to exercise. During each walk, she enjoys finding the greatest common factor (GCF) of the Interpasture Paths that she traverses. For instance, the walk designated 1-4-2 touches I-16 and I-6 which have the greatest common factor of 2 (since 2 properly divides into 16 and 6 but no larger integer does).

As she walks the pastures day after day, she takes all the possible routes from pasture 1 to pasture 2 and remembers each of the GCFs. After she has taken every possible walk once, she computes the least common multiple (LCM) of all the GCFs. For this example, the two GCF values are 2 and 3 (GCF(6,16)=2 and GCF(3,9)=3), so the LCM is 6.

For large networks of paths, Bessie might get tired of all the walking, but she really wants to know the LCM for every map. Calculate that number for her.

输入:

* Line 1: N

* Lines 2..N+1: These N lines represent the symmetric Interpasture Path connectivity matrix of the pastures. Line L shows the connectivity between pasture L-1 and the other pastures with its N space-separated integers. The first integer on each line is the Interpasture Path number that connects pasture L-1 and and pasture 1; the second integer is the IP number connecting pasture L-1 and pasture 2; etc. If pasture A connects to pasture B, then pasture B connects to Pasture A. When no Interpasture Path is available, the integer is 0.

输出:

A single line with a single integer that is the LCM of the GCFs of all the possible walks from pasture 1 to pasture 2. It is guaranteed that the answer will contain 100 or fewer digits.

样例输入:

4
0 0 3 16
0 0 9 6
3 9 0 0 
16 6 0 0

样例输出:

6

解题代码:

//* @author:alpc12
import java.io.*;
import java.util.*;
import java.math.*;


public class Main {
	
  static int N = 26; 
  int n;
  int M;
  int[][] adj = new int[26][26];
  boolean[] chk = new boolean[26];
	
  boolean DFS(int K, int m) {
   chk[m] = true;
   if(m == 1) 
       return true;
   int i;
   for(i = 0; i < n; ++i) if(!chk[i])
	if(adj[m][i]!=0 && adj[m][i] % K == 0)
         if(DFS(K, i))
		return true;
	return false;
   }
	
 BigInteger GCD(BigInteger x, BigInteger y) {
   if(x.compareTo(y) < 0) 
	return GCD(y, x);
   while(y.compareTo(BigInteger.ZERO) > 0) {
 	BigInteger tmp = y;
	y = x.mod(y);
	x = tmp;
   }
   return x;
 }
	
 BigInteger LCM(BigInteger x, BigInteger y) {
   BigInteger ret = x.multiply(y);
   ret = ret.divide(GCD(x, y));
   return ret;
  }
	
  void run() {
   Scanner cin = new Scanner(System.in);
   n = cin.nextInt();
   int i, j;
   M = 0;
   for(i = 0; i < n; ++i)
	for(j = 0; j < n; ++j) {
         adj[i][j] = cin.nextInt();
	  if(adj[i][j] > M)
	    M = adj[i][j];
	}
		
    BigInteger ans = new BigInteger("1");
	for(i = 1; i <= M; ++i) {
	  for(j = 0; j < n; ++j)
	    chk[j] = false;
	  if(DFS(i, 0)) {
//	    System.out.println(i + " " + ans);
	    ans = LCM(ans, new BigInteger(""+i));
	   }
	}
	System.out.println(ans);
    }

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

  }

}

  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1