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

1 ≤ T ≤ 5

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 //测试是否为三角形
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<T;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<M;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)
}
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;
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]))){
node=nodes[k][1];
break;
}else if((node==nodes[k][1])&&(!success.contains(nodes[k][0]))){
node=nodes[k][0];
break;
}
}
if(i!=0){
for(int suc:success){
for(int j=0;j<nodes.length;j++){
if(!list.contains(suc)){
flag=false;
list=swap(list);
break;
}
}
}
}
}
if(num01s.contains(node)){
flags[num01s.indexOf(node)]=false;
flag=false;
}
}
}
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>=0;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<=n;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)>k);
}

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++){
}
for(int i=yindex;i>=0;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<max;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>();
int s=start;
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>=0;j--){
}
s=struct.get(i).get(0);
break;
}
}
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：

——20130409

SaaS 模式云数据仓库必修课

|
4天前
|
Java 开发者
9 0
|
4天前
|

Java面试题：在Java中，对象何时可以被垃圾回收？编程中，如何更好地做好垃圾回收处理？
Java面试题：在Java中，对象何时可以被垃圾回收？编程中，如何更好地做好垃圾回收处理？
14 0
|
3天前
|

【5月更文挑战第72天】 在现代软件开发中，尤其是Java应用开发领域，并发编程是一个无法回避的重要话题。随着多核处理器的普及，合理利用并发机制对于提高软件性能、响应速度和资源利用率具有重要意义。本文旨在探讨Java并发编程的核心概念、线程安全的策略以及性能优化技巧，帮助开发者构建高效且可靠的并发应用。通过实例分析和理论阐述，我们将揭示在高并发环境下如何平衡线程安全与系统性能之间的关系，并提出一系列最佳实践方法。
|
4天前
|
Java 数据格式
Java面试题：简述Java Socket编程的基本流程，包括客户端和服务器的创建与通信。
Java面试题：简述Java Socket编程的基本流程，包括客户端和服务器的创建与通信。
11 0
|
4天前
|

Java面试题：请列举三种常用的设计模式，并分别给出在Java中的应用场景？请分析Java内存管理中的主要问题，并提出相应的优化策略？请简述Java多线程编程中的常见问题，并给出解决方案
Java面试题：请列举三种常用的设计模式，并分别给出在Java中的应用场景？请分析Java内存管理中的主要问题，并提出相应的优化策略？请简述Java多线程编程中的常见问题，并给出解决方案
13 0
|
4天前
|

Java面试题：请解释Java并发工具包中的主要组件及其应用场景，请描述一个使用Java并发框架（如Fork/Join框架）解决实际问题的编程实操问题
Java面试题：请解释Java并发工具包中的主要组件及其应用场景，请描述一个使用Java并发框架（如Fork/Join框架）解决实际问题的编程实操问题
11 0
|
4天前
|

Java面试题：解释Java内存模型的无锁编程支持，并讨论其优势和局限性，解释Java中的CompletableFuture的工作原理，并讨论其在异步编程中的应用
Java面试题：解释Java内存模型的无锁编程支持，并讨论其优势和局限性，解释Java中的CompletableFuture的工作原理，并讨论其在异步编程中的应用
9 0
|
Java

796 0
|
3天前
|
Java 调度
Java线程的六种状态
Java线程有六种状态： 初始（NEW）、运行（RUNNABLE）、阻塞（BLOCKED）、等待（WAITING）、超时等待（TIMED_WAITING）、终止（TERMINATED）。
13 1
|
4天前
|

Java面试题：请解释Java内存模型(JMM)是什么，它如何保证线程安全？
Java面试题：请解释Java内存模型(JMM)是什么，它如何保证线程安全？
35 13