首页 > 专题系列 > Java解POJ > POJ 1659 Frogs’ Neighborhood [解题报告] Java
2013
11-10

POJ 1659 Frogs’ Neighborhood [解题报告] Java

Frogs’ Neighborhood

问题描述 :

未名湖附近共有N个大小湖泊L1, L2, …, Ln(其中包括未名湖),每个湖泊Li里住着一只青蛙Fi(1 ≤ iN)。如果湖泊LiLj之间有水路相连,则青蛙FiFj互称为邻居。现在已知每只青蛙的邻居数目x1, x2, …, xn,请你给出每两个湖泊之间的相连关系。

输入:

第一行是测试数据的组数T(0 ≤ T ≤ 20)。每组数据包括两行,第一行是整数N(2 < N < 10),第二行是N个整数,x1, x2,…, xn(0 ≤ xiN)。

输出:

对输入的每组测试数据,如果不存在可能的相连关系,输出"NO"。否则输出"YES",并用N×N的矩阵表示湖泊间的相邻关系,即如果湖泊i与湖泊j之间有水路相连,则第i行的第j个数字为1,否则为0。每两个数字之间输出一个空格。如果存在多种可能,只需给出一种符合条件的情形。相邻两组测试数据之间输出一个空行。

样例输入:

3
7
4 3 1 5 4 2 1 
6
4 3 1 4 2 0 
6
2 3 1 1 2 1 

样例输出:

YES
0 1 0 1 1 0 1 
1 0 0 1 1 0 0 
0 0 0 1 0 0 0 
1 1 1 0 1 1 0 
1 1 0 1 0 1 0 
0 0 0 1 1 0 0 
1 0 0 0 0 0 0 

NO

YES
0 1 0 0 1 0 
1 0 0 1 1 0 
0 0 0 0 0 1 
0 1 0 0 0 0 
1 1 0 0 0 0 
0 0 1 0 0 0 

解题代码:

//* @author: [email protected]
import java.io.*;
import java.util.*;
public class Main
{
 static int[][] p;
 static ri[] arr;
 public static void main(String[] args) throws IOException
 {
   InputStreamReader is=new InputStreamReader(System.in);
   BufferedReader in=new BufferedReader(is);
   int n=Integer.parseInt(in.readLine());
   while((n--)!=0)
   {
	int m=Integer.parseInt(in.readLine());
	p=new int[m][m];
	arr=new ri[m];
	String[] ss=in.readLine().split(" ");
	for(int i=0;i< m;i++)
		arr[i]=new ri(Integer.parseInt(ss[i]),i);
	
	int cnt=0;
	boolean bb=true;
	while(bb)
	{
		Arrays.sort(arr,cnt,m);
		int uu=arr[cnt].num;
		for(int i=0;i< arr[cnt].num;i++)
		{
			arr[cnt+1+i].num--;
			p[arr[cnt].n][arr[cnt+1+i].n]=1;
			p[arr[cnt+1+i].n][arr[cnt].n]=1;
			if(arr[cnt+1+i].num< 0)
			{
				bb=false;
				break;
			}
		}
		cnt++;
		if(cnt==m)break;
	}
	if(!bb)System.out.println("NO");
	else{
		System.out.println("YES");
		for(int i=0;i< m;i++)
		{
			for(int j=0;j< m;j++)
				System.out.print(p[i][j]+" ");
			System.out.println();
		}
	}
	System.out.println();
  }
 }
}
class ri implements Comparable< ri>
{
	int num;
	int n;
	public ri(int a,int b)
	{
		num=a;
		n=b;
	}
	@Override
	public int compareTo(ri arg0) {
		
		return arg0.num-num;
	}
}

  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。