时间限制: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
三角形的判断
对于给定三条边a,b,c，当且仅当
1.a+b>c
2.b+c>a
3.a+c>b
同时成立时才能组成三角形，但如果a<=b<=c，则只要满足a+b>c即可组成一个三角形。
所以对于一个给定的长度大于2的数组，可以将其先排序（假设升序），只要存在i，使得ai+ai+1>ai+2成立，就说明以该数组中的数字为边可以组成三角形。
思路：
以下是小数据时的代码：
#include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> using namespace std; #define MAX 100 #define INF 0x03F3F3F3F//太大可能会溢出 int path[MAX][MAX], map[MAX][MAX], cost[MAX][MAX], tmp[MAX]; void Floyd(int N) { for(int k = 0; k != N; ++k) for(int i = 0; i != N; ++i) for(int j = 0; j != N; ++j) if(cost[i][j] > cost[i][k] + cost[k][j]) { cost[i][j] = cost[i][k] + cost[k][j]; path[i][j] = path[i][k]; } } int cmp (const void *a, const void *b ){ return *(int *)a - *(int *)b; //升序排序 } int main() { int T, N, M, s, t; int a, b, len; scanf("%d", &T); for(int i = 1; i <= T; ++i) { printf("Case #%d:\n", i); scanf("%d", &N); //初始化map、cost、path数组 for(int j = 0; j != N; ++j) for(int k = 0; k != N; ++k) { if(j == k) map[j][k] = cost[j][k] = 0; else map[j][k] = cost[j][k] = INF; path[j][k] = k; } //输入边长 for(int j = 1; j != N; ++j) { scanf("%d%d%d", &a, &b, &len); map[a - 1][b - 1] = map[b - 1][a - 1] = cost[a - 1][b - 1] = cost[b - 1][a - 1] = len; } //测试 Floyd(N); scanf("%d", &M); while(M--) { scanf("%d%d", &s, &t); int cnt = 0; s = s - 1; t = t - 1; int u; do{ u = path[s][t]; tmp[cnt++] = map[s][u]; s = u; }while(s != t); qsort(tmp, cnt, sizeof(int), cmp); int flag = 0; if(cnt > 2) { for(int j = 0; j != cnt - 2; ++j) if(tmp[j] + tmp[j + 1] > tmp[j + 2]) { flag = 1; break; } } if(flag) printf("Yes\n"); else printf("No\n"); } } return 0; }
大数据1 ≤ len ≤ 1000000000的处理
根据上述三角形的判断，对于大数据，可利用斐波纳挈数列。
对于一个长度为n的数组，其最大值为max，假设Fibonacci(x) = max，则不能组成三角形的极端情况是n==x并且数组中的数字呈斐波那契数列排列；换言之，只要n>x，则数组中一定存在三个数，以它们为三条边能组成三角形。
由于Fibonacci(45)>1000000000，所以，只要求得的最短路径的条数不小于45，就一定能组成三角形，不需要判断，直接输出yes即可。
原文：http://www.cnblogs.com/redhead/p/3651621.html