Saber
Time Limit: 2 Seconds Memory Limit: 65536 KB Score: 1
Saber is a Class in the Holy Grail War. This Class is regarded as one of the most powerful Class.
Saber is a tree-lover. She loves all kinds of trees. One day, she suddenly comes up with a curious problem. She wants to know that in the path between x and y, whether it exists that when we choose three different edges i,j,k, the length of these three edges can build a triangle. Now she wants you to solve this problem.
Input
There are multiple test cases. The first line of input contains an integer T(T ≤ 5), indicating the number of test cases. For each test case:
The first line contains one integer N(1 ≤ N ≤ 100000), indicating the number of tree’s vertices. In the following N-1 lines, there are three integers x, y, w (1 ≤ w ≤ 1000000000), indicating an edge weighted w between x and y.
In the following line also contains one integer Q(1 ≤ Q ≤ 100000), indicating the number of queries. In the following Q lines, there are two integers x, y, indicating a query between x and y.
Output
For each test case output ‘Case #i:’ in the first line, i equals to the case number. Then for every query output ‘Yes’ or ‘No’ in one line.
Sample Input
/
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
Sample Output
Case #1: No Yes Case #2: No Yes
解题思路
1、因为题目说明了是树，所以保证给出的数据是一定能通的。2、存在的路径中找到是否存在三条边构成三角形，此时的路径是两点的唯一路径，不包括其他死胡同的边（哪怕是相通的）。3、斐波那契数列与三角形的关联（破 TLE）。
AC 代码（每次 DFS 版）
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=100000+100; struct node { int e,w; //node(int e,int w):e(e),w(w){} // 推荐这种写法，用到时，无需再定义声明 }; vector<node> ve[maxn]; int vis[maxn], num[60]; int n,m,s,e,flag,found; void init() { for(int i=0;i<=maxn;i++) // ve[i].clear(); vector<node>().swap(ve[i]); // 这种写法比 clear() 更彻底清除 m=n-1; mem(vis,0); } int ok(int a,int b,int c) { return a+b>c; } void dfs(int s,int step) { // 50的标记是来自于斐波那契数列上限46就达到了此题目中的最大值 // 所以顶峰是45时，再无论加一条边就肯定能找到构成的三角形的三条边 if(step>50 || found) return; if(s==e) { found=1; if(step>50) { flag=1; return; } sort(num,num+step); int a,b,c; for(int i=2;i<step;i++) // 判断是否可以构成三角形 { a=num[i-2], b=num[i-1], c=num[i]; if(ok(a,b,c)) { flag=1; return; } } return; } for(int i=0;i<ve[s].size();i++) { if(!vis[ve[s][i].e]) { vis[ve[s][i].e]=1; num[step]=ve[s][i].w; dfs(ve[s][i].e,step+1); vis[ve[s][i].e]=0; } } return; } int main() { int T,kase=0; scanf("%d",&T); while(T-- && ~scanf("%d",&n)) { init(); int u,v,w,q; node nd1,nd2; for(int i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); nd1.e=v; nd1.w=w; nd2.e=u; nd2.w=w; ve[u].push_back(nd1); ve[v].push_back(nd2); } scanf("%d",&q); printf("Case #%d:\n",++kase); for(int i=0;i<q;i++) { scanf("%d%d",&s,&e); found=flag=0; vis[s]=1; // 别忘记一开始就已经经过的这个点s dfs(s,0); vis[s]=0; // found == 0 是因为在到终点的途中就已经超过了阈值，所以就可以马上return，此时的found一定等于0 puts(!found || flag?"Yes":"No"); } } return 0; }
AC 代码（公共祖先版，仅需一次 DFS）
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=100100; int n,tp; int dep[maxn], dis[maxn], fa[maxn], head[maxn], num[maxn]; struct edge { int to,w,nx; }eds[2*maxn]; // *2 是因为是无向图 void init() { tp=0; mem(head,-1); } void addEdge(int u, int v, int w) { eds[tp].to=v; eds[tp].w=w; eds[tp].nx=head[u]; head[u]=tp++; } void dfs(int u, int f, int w, int d) { int v; fa[u]=f; dis[u]=w; dep[u]=d; for(int i=head[u];i!=-1;i=eds[i].nx) { v=eds[i].to; w=eds[i].w; if(v!=f) dfs(v,u,w,d+1); // v!=f 避免从 1->2 又反过来 2->1 的情况 } } int main() { int T,kase=0; scanf("%d",&T); while(T-- && ~scanf("%d",&n)) { init(); int u,v,w; for(int i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&w); addEdge(u,v,w); addEdge(v,u,w); } dfs(1,0,0,1); int q,len; scanf("%d",&q); printf("Case #%d:\n",++kase); for(int i=0;i<q;i++) { scanf("%d%d",&u,&v); len=0; while(dep[u]>dep[v]&&len<50) num[len++]=dis[u], u=fa[u]; // 在公共祖先的一侧且 u 在 v 的后面 while(dep[v]>dep[u]&&len<50) num[len++]=dis[v], v=fa[v]; // 在公共祖先的一侧且 v 在 u 的后面 while(u!=v&&len<50) num[len++]=dis[v], v=fa[v], num[len++]=dis[u], u=fa[u]; // 在公共祖先的两侧 sort(num,num+len); int ok=0; for(int j=0;j<len-2;j++) { if(num[j]+num[j+1]>num[j+2]) { ok=1; break; } } puts(ok?"Yes":"No"); } } return 0; }
