时间限制:4000ms
单点时限:2000ms
内存限制:256MB
描述
有一棵树，树上有只毛毛虫。它在这棵树上生活了很久，对它的构造了如指掌。所以它在树上从来都是走最短路，不会绕路。它还还特别喜欢三角形，所以当它在树上爬来爬去的时候总会在想，如果把刚才爬过的那几根树枝/树干锯下来，能不能从中选三根出来拼成一个三角形呢？
输入
输入数据的第一行包含一个整数 T，表示数据组数。
接下来有 T
组数据，每组数据中：
第一行包含一个整数 N，表示树上节点的个数（从 1到 N
标号）。
接下来的 N-1
行包含三个整数 a, b, len，表示有一根长度为 len的树枝/树干在节点
a和节点 b
之间。
接下来一行包含一个整数 M，表示询问数。
接下来M行每行两个整数 S, T，表示毛毛虫从 S爬行到了
T，询问这段路程中的树枝/树干是否能拼成三角形。
1 ≤ T ≤ 5
小数据：1 ≤ N ≤ 100, 1 ≤M ≤ 100, 1 ≤ len ≤ 10000
大数据：1 ≤ N ≤ 100000,1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000
输出
对于每组数据，先输出一行"Case#X:",其中X为数据组数编号，从 1开始。
接下来对于每个询问输出一行，包含"Yes"或“No”，表示是否可以拼成三角形。
样例输入
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
这个题昨天做的时候总是报RE，也就是运行时错误Runtime Error，原因是它那个测试系统不允许创建多个类，即使是内部类也不行，办法就是改写成数组形式表示。
思路：
1、读取数据，建立图
2、广度优先遍历，找到目的点。这个过程找到的肯定是最短路，因为这是一棵树，两点之间只有一条通路（不重复的情况下）。遍历过程中保存每个点遍历的时候的父亲节点，这样就能够知道走过了哪些节点。
3、遍历任意三条边的组合是否能够组成三角形。
我自己创建了一些测试数据，感觉大数据时应该也还可以，不会超时。只有最后一步看似效率比较低，实际上有的文章说，当边数超过50时，一定能够组成三角形，所以实际上它每次都不会遍历那么多次就返回了。
import java.util.*;
import java.io.*;
/*class MyNode
{
int id;
int flag=0;
List<MyNode> adjacent=null;
MyNode parent=null;
public MyNode(int id)
{
this.id=id;
adjacent=new ArrayList<MyNode>();
}
public void addAdjacnet(MyNode n)
{
this.adjacent.add(n);
}
}*/
public class Main {
int id[];
int flag[];
List<Integer> adjacent[];
int parent[];
public void run()
{
Scanner in = new Scanner(System.in);
int num=in.nextInt();
for(int i=0;i<num;i++)
{
int size=in.nextInt();
id=new int[size];
flag=new int[size];
adjacent=new ArrayList[size];
for(int j=0;j<adjacent.length;j++)
{
adjacent[j]=new ArrayList<Integer>();
}
parent=new int[size];
Map<String,Integer> edges=new HashMap<String,Integer>();
for(int k=0;k<size;k++)
{
id[k]=k+1;
flag[k]=0;
parent[k]=-1;
}
for(int j=0;j<size-1;j++)
{
int start=in.nextInt();
int end=in.nextInt();
int length=in.nextInt();
edges.put(start+" "+end, length);
edges.put(end+" "+start, length);
adjacent[start-1].add(end);
adjacent[end-1].add(start);
}
//System.out.println(nodes);
int queryTimes=in.nextInt();
System.out.println("Case #"+(i+1)+":");
for(int j=0;j<queryTimes;j++)
{
int startNode=in.nextInt();
int endNode=in.nextInt();
String result=find(edges,startNode,endNode);
for(int k=0;k<size;k++)
{
parent[k]=-1;
flag[k]=0;
}
System.out.println(result);
}
}
}
public static void main(String args[]) throws IOException
{
Main m=new Main();
m.run();
}
private String find( Map<String,Integer> edges,
int startNode, int endNode) {
Queue<Integer> queue=new LinkedList<Integer>();
flag[startNode-1]=1;
queue.add(startNode);
while(!queue.isEmpty())
{
int node=queue.poll();
flag[node-1]=2;
if(node==endNode)
{
return judge(node,edges);
}
for(int n:adjacent[node-1])
{
if(flag[n-1]==0)
{
flag[n-1]=1;
parent[n-1]=node;
queue.add(n);
//System.out.println(queue.size());
}
}
}
return "No";
}
private String judge(int node,Map<String,Integer> edges) {
List<Integer> list=new ArrayList<Integer>();
while(parent[node-1]!=-1)
{
Integer length=edges.get(node+" "+parent[node-1]);
if(length==null)
return "No";
list.add(length);
node=parent[node-1];
}
if(list.size()<3)
return "No";
for(int i=0;i<list.size();i++)
{
for(int j=i+1;j<list.size();j++)
{
for(int k=j+1;k<list.size();k++)
{
int temp[]=new int[3];
temp[0]=list.get(i);
temp[1]=list.get(j);
temp[2]=list.get(k);
Arrays.sort(temp);
if(temp[0]+temp[1]>temp[2])
return "Yes";
}
}
}
return "No";
}
}
编程之美热身赛——树上三角形（解决RE Runtime Error）,布布扣,bubuko.com
编程之美热身赛——树上三角形（解决RE Runtime Error）
原文：http://blog.csdn.net/smartxxyx/article/details/23201891