2013编程之美资格赛之树上的三角形（Java实现）

描述
有一棵树，树上有只毛毛虫。它在这棵树上生活了很久，对它的构造了如指掌。所以它在树上从来都是走最短路，不会绕路。它还还特别喜欢三角形，所以当它在树上爬来爬去的时候总会在想，如果把刚才爬过的那几根树枝/树干锯下来，能不能从中选三根出来拼成一个三角形呢？


输入
输入数据的第一行包含一个整数 T，表示数据组数。


接下来有 T 组数据，每组数据中：


第一行包含一个整数 N，表示树上节点的个数（从 1 到 N 标号）。


接下来的 N-1 行包含三个整数 a, b, len，表示有一根长度为 len 的树枝/树干在节点 a 和节点 b 之间。


接下来一行包含一个整数 M，表示询问数。


接下来M行每行两个整数 S, T，表示毛毛虫从 S 爬行到了 T，询问这段路程中的树枝/树干是否能拼成三角形。


输出
对于每组数据，先输出一行"Case #X:",其中X为数据组数编号，从 1 开始。


接下来对于每个询问输出一行，包含"Yes"或“No”，表示是否可以拼成三角形。


数据范围
1 ≤ T ≤ 5


小数据：1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ len ≤ 10000


大数据：1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000


样例输入
2
5
1 2 5
1 3 20
2 4 30
4 5 15
2
3 4
3 5
5
1 4 32
2 3 100
3 5 45
4 5 60
2
1 4
1 3
样例输出
Case #1:
No
Yes
Case #2:
No
Yes


主要算法：
define results
get T
for 1 to T
get N
for 1 to N-1
get 边
getStruct 边s //构造类树
get M
define result
for 1 to M
get S,E
get S,E 到树根的路劲
get S,E 到树根的路劲的非公共节点
get S,E 间的路劲
get values S,E间路劲的段长度集合
sort(values)
result+=Test values//测试是否为三角形
results add result
print results


Test 算法
for i=2 to values.length
if values[i-2]+vaules[i-1] values[i]
return true
return false

程序：

import java.util.*;

public class Main {

 public static void main(String[] args){

 Scanner sc=new Scanner(System.in);

 int T=sc.nextInt();

 String[] results=new String[T];

 for(int i=0;i i++){

 int N=sc.nextInt(); 

 int tempN=N-1;

 int[][] nodes=new int[tempN][3];

 for(int j=0;j tempN;j++){

 nodes[j][0]=sc.nextInt();

 nodes[j][1]=sc.nextInt();

 nodes[j][2]=sc.nextInt();

 List ArrayList Integer struct=getStruct(nodes);

 int M=sc.nextInt();

 String result="";

 for(int j=0;j j++){

 int start=sc.nextInt();

 int end=sc.nextInt();

 result=result+" "+getResult(start,end,struct,nodes);

 results[i]=result.trim();

 printResult(results);

 private static List ArrayList Integer getStruct(int[][] nodes) {

 ArrayList Integer num01s=new ArrayList Integer (nodes.length);

 int[] temp=new int[nodes.length+1];

 for(int i=0;i temp.length;i++){

 temp[i]=0;

 for(int i=0;i nodes.length;i++){

 temp[(nodes[i][0]-1)]++;

 temp[(nodes[i][1]-1)]++;

 for(int i=0;i temp.length;i++){

 if(temp[i]==1)

 num01s.add(i+1);

 int structLength=num01s.size()-1;

 List ArrayList Integer struct=new ArrayList ArrayList Integer (structLength);

 boolean[] flags=new boolean[structLength+1];

 for(int i=0;i flags.length;i++){

 flags[i]=true;

 List Integer success=new ArrayList Integer (nodes.length+1);

 for(int i=0;i structLength;i++){

 ArrayList Integer list=new ArrayList Integer (nodes.length+1);

 for(int j=0;j flags.length;j++){

 if(flags[j]){

 flags[j]=false;

 list.add(num01s.get(j));

 success.add(num01s.get(j));

 break;

 int node=list.get(0);

 boolean flag=true;

 while(flag){

 for(int k=0;k nodes.length;k++){

 if((node==nodes[k][0]) (!success.contains(nodes[k][1]))){

 list.add(nodes[k][1]);

 node=nodes[k][1];

 success.add(node);

 break;

 }else if((node==nodes[k][1]) (!success.contains(nodes[k][0]))){

 list.add(nodes[k][0]);

 node=nodes[k][0];

 success.add(node);

 break;

 if(i!=0){

 int add=list.get(list.size()-1);

 for(int suc:success){

 for(int j=0;j nodes.length;j++){

 if((suc==nodes[j][0] add==nodes[j][1])||(suc==nodes[j][1] add==nodes[j][0])){

 if(!list.contains(suc)){

 list.add(suc);

 flag=false;

 list=swap(list);

 break;

 if(num01s.contains(node)){

 flags[num01s.indexOf(node)]=false;

 flag=false;

 struct.add(list);

 return struct;


 private static ArrayList Integer swap(ArrayList Integer list) {

 ArrayList Integer temp=new ArrayList Integer (list.size());

 for(int i=list.size()-1;i i--){

 temp.add(list.get(i));

 return temp;

 private static String getResult(int start, int end,

 List ArrayList Integer struct, int[][] nodes) {

 ArrayList Integer startPath=getNodePath(start,struct);

 ArrayList Integer endPath=getNodePath(end,struct);

 ArrayList Integer SE=new ArrayList Integer (nodes.length+1);

 int common=getCommonNode(startPath,endPath);

 if(startPath.indexOf(common)==0){

 SE=getPath(common,endPath);

 }else if( endPath.indexOf(common)==0){

 SE=getPath(common,startPath);

 }else {

 SE=getPath(common,startPath,endPath);

 int[] values=getValue(SE,nodes);

 sort(values);

 return echo(values);

 private static ArrayList Integer getPath(int common,

 ArrayList Integer list) {

 ArrayList Integer l=new ArrayList Integer (list.size());

 int n=list.indexOf(common);

 for(int i=0;i i++){

 l.add(list.get(i));

 return l;

 private static void sort(int[] values) {

 for(int i=0;i values.length;i++){

 int min=i;

 for(int j=i+1;j values.length;j++){

 if(values[j] values[min])

 min=j;

 if(i!=min){

 int temp=values[i];

 values[i]=values[min];

 values[min]=temp;

 private static String echo(int[] values) {

 if(values.length 3)

 return "No";

 String result="No";

 for(int i=2;i values.length;i++){

 if(judge(values[i-2],values[i-1],values[i])){

 result="Yes";

 break;

 return result;

 private static boolean judge(int i, int j, int k) {

 return ((i+j) 

 private static int[] getValue(ArrayList Integer sE,int[][] nodes) {

 int[] values=new int[sE.size()-1];

 for(int i=0;i values.length;i++){

 for(int j=0;j nodes.length;j++){

 int x=sE.get(i);

 int y=sE.get(i+1);

 if(nodes[j][0]==x nodes[j][1]==y){

 values[i]=nodes[j][2];

 break;

 }else if (nodes[j][1]==x nodes[j][0]==y){

 values[i]=nodes[j][2];

 break;

 return values;

 private static ArrayList Integer getPath(int m, 

 ArrayList Integer xList, ArrayList Integer yList) {

 ArrayList Integer path=new ArrayList Integer (xList.size()+yList.size());

 int xindex=xList.indexOf(m);

 int yindex=yList.indexOf(m);

 for(int i=0;i xindex;i++){

 path.add(xList.get(i));

 for(int i=yindex;i i--){

 path.add(yList.get(i));

 return path;

 private static int getCommonNode(ArrayList Integer xList,

 ArrayList Integer yList) {

 int max=xList.size();

 int c=-1;

 for(int i=0;i i++){

 int temp=xList.get(i);

 if(yList.contains(temp)){

 c=temp;

 break;

 return c;

 private static ArrayList Integer getNodePath(int start,

 List ArrayList Integer struct) {

 ArrayList Integer temp=new ArrayList Integer 

 temp.add(start);

 int s=start;

 int head=struct.get(0).get(0);

 int slength=struct.size();

 boolean flag=true;

 while(flag){

 for(int i=0;i slength;i++){

 if(struct.get(i).contains(s) s!=struct.get(i).get(0)){

 int x=struct.get(i).indexOf(s);

 for(int j=(x-1);j j--){

 temp.add(struct.get(i).get(j));

 s=struct.get(i).get(0);

 break;

 if(head==s){

 flag=false;

 return temp;

 private static void printResult(String[] result) {

 for(int i=0;i result.length;i++){

 System.out.println("Case #"+(i+1)+":");

 String[] words=result[i].split(" ");

 for(String word:words)

 System.out.println(word);

}

这也是同样了，通过了比赛系统小数据测试，大数据测试未知。

——20130408

PS：

今天早晨数据出来了，这道题的大数据测试时TLE，超时。在情理之中。原因见博文《2013编程之美资格赛之大数据测试（Java实现）》

——20130409

Java实现图书管理系统 本篇文章是对目前Java专栏已有内容的一个总结练习，希望各位小主们在学习完面向对象的知识后，可以阅览本篇文章后，自己也动手实现一个这样的demo来加深总结应用已经学到知识并进行巩固。
Java实现拼图小游戏（1）—— JFrame的认识及界面搭建 如果要在某一个界面里面添加功能的话，都在一个类中，会显得代码难以阅读，而且修改起来也会很困难，所以我们将游戏主界面、登录界面、以及注册界面都单独编成一个类，每一个类都继承JFrame父类，并且在类中创建方法来来实现页面
Java实现拼图小游戏（7）—— 计步功能及菜单业务的实现 注意由于我们计步功能的步数要在重写方法中用到，所以不能将初始化语句写在方法体内，而是要写在成员位置。在其名字的时候也要做到“见名知意”，所以我们给它起名字为step
Java实现拼图小游戏（7）—— 作弊码和判断胜利 当我们好不容易把拼图复原了，但是一点提示也没有，完全看不出来是成功了，那么我们就需要有判断胜利的功能去弹出“成功”类的图片，以便于玩家选择是重新开始还是退出小游戏