首页 > 专题系列 > Java解POJ > POJ 3256 Cow Picnic [解题报告] Java
2013
11-12

POJ 3256 Cow Picnic [解题报告] Java

Cow Picnic

问题描述 :

The cows are having a picnic! Each of Farmer John’s K (1 ≤ K ≤ 100) cows is grazing in one of N (1 ≤ N ≤ 1,000) pastures, conveniently numbered 1…N. The pastures are connected by M (1 ≤ M ≤ 10,000) one-way paths (no path connects a pasture to itself).

The cows want to gather in the same pasture for their picnic, but (because of the one-way paths) some cows may only be able to get to some pastures. Help the cows out by figuring out how many pastures are reachable by all cows, and hence are possible picnic locations.

输入:

Line 1: Three space-separated integers, respectively: K, N, and M

Lines 2..K+1: Line i+1 contains a single integer (1..N) which is the number of the pasture in which cow i is grazing.

Lines K+2..M+K+1: Each line contains two space-separated integers, respectively A and B (both 1..N and A != B), representing a one-way path from pasture A to pasture B.

输出:

Line 1: The single integer that is the number of pastures that are reachable by all cows via the one-way paths.

样例输入:

2 4 4
2
3
1 2
1 4
2 3
3 4

样例输出:

2

温馨提示:

The cows can meet in pastures 3 or 4.

解题代码:

//* @author: SmilingWang
import java.util.*;

public class Main {
 static LinkedList< Integer> set = new LinkedList< Integer>();
 static TreeSet< Integer> tmset = new TreeSet< Integer>();
 static int[][] path;
 static boolean[][] use;
 static ArrayList[] table;
 public static void main(String[] args){
   Scanner in = new Scanner(System.in);
   int k, m, n;
   k = in.nextInt();
   n = in.nextInt();
   m = in.nextInt();
   int g[] = new int[k];
   for(int i = 0; i < k; i++){
	g[i] = in.nextInt();
   }
   path = new int[n+1][n+1];
   table = new ArrayList[n+1];
   for(int i = 1; i <= n; i++){
	path[i][i] = 1;
	table[i] = new ArrayList< Integer>();
	table[i].add(i);
   }
   for(int i = 0; i < m; i++){
	int a = in.nextInt();
	int b = in.nextInt();
	path[a][b] = 1;
	table[a].add(b);
   }
		
   for(int i = 0; i < k; i++){
     use = new boolean[n+1][n+1];
     search(g[i],n);
     set.addAll(tmset);
     tmset.clear();
    }
    Iterator< Integer> iter = set.iterator();
    int[] count= new int[n+1];
    int   ncount = 0;
    while(iter.hasNext()){
	int tm = iter.next();
	count[tm]++;
	if(count[tm] >= k){
		ncount++;
	}
    }
     System.out.println(ncount);
   }
	
  public static void search(int start, int n){
   for(int i = 0; i < table[start].size(); i++){
	int j = (Integer)table[start].get(i);
	if(path[start][j] > 0  && !use[start][j]){
		tmset.add(j);
		use[start][j] = true;
		search(j, n);
	}
   }
 }
}

  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  4. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。