注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

长风明志的博客

不要也不能做下一个谁,应该且可以做第一个自己

 
 
 

日志

 
 

【2013编程之美资格赛】 树上的三角形  

2013-04-13 18:28:54|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

时间限制: 2000ms 内存限制: 256MB

描述

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

输入

输入数据的第一行包含一个整数 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
小数据:
状态: Accepted
大数据:
状态: Memory Limit Exceeded


#include <iostream> #include <string> #include <vector> #include <map> #include <cmath> using namespace std; map<int,int> adj; //记录遍历节点时从开始节点到目的节点路径上的各个节点 int hasFound; void DFS(vector<vector<int> > vecAdjMatrix,vector<int> visited,int n,int S,int T) //深度优先遍历邻接矩阵表示的图,从而找到S到T的路径 { visited[S-1]=1; for(int i=0;i<n;i++) { if(hasFound) //已经找到目标节点则一直退出函数直到退出最外一层函数 { break; } if(vecAdjMatrix[S-1][i]!=0&&!visited[i]) { adj[S]=i+1; //记录在遍历路径上该节点的下一个节点ID值 if(i+1==T) //找到T了 { hasFound=1; break; } DFS(vecAdjMatrix,visited,n,i+1,T); //深度遍历邻接节点 } } } // //生成组合并判断构成该组合的某3条边是否能生成三角形,若能则返回true,若不能则返回false //n: 原来的元素总个数 //m: 生成的子排列的元素个数 bool combination(vector<int> vecInput,int n,int m) //生成组合P(n,m) { //if(0==n||0==m||n<m) //检查输入的参数是否满足条件 //{ // exit(1); //} int size=n; int position; //对应数字需要加1的下标位置 long count=0; //组合数计数 vector<int> vecOrder; //存放组合的下标 如{1,2,3} 表示vecInput中的下标0,1,2对应的字符 for(int i=1;i<=m;i++) //初始化组合的下标,如{1,2,3} { vecOrder.push_back(i); } position=m-1; //一开始从最右边开始执行加1操作 while(1) { count++; //组合数加1 //cout<<count<<": "; //cout<<"{"; //输出一个排列 //for(int i=0;i<m;i++) //{ // cout<<vecInput[vecOrder[i]-1]<<" "; //} //cout<<"}"<<endl; //判断3边是否能构成三角形 int a=vecInput[vecOrder[0]-1],b=vecInput[vecOrder[1]-1],c=vecInput[vecOrder[2]-1]; //三条边 if(a+b>c&&a+c>b&&b+c>a&&abs(a-b)<c&&abs(a-c)<b&&abs(b-c)<a) { return true; } if(vecOrder[0]==(size-m+1)) //表示已经到了最后一个排列 { break; } if((position==m-1&&vecOrder[position]<size)||(position<m-1&&vecOrder[position]+1<vecOrder[position+1])) //要求最右边的数字不等于size才加1&&不是最右边的数字加1后小于其右边的数 { vecOrder[position]++; continue; } else { position--; //往左移一位 if(vecOrder[position]+1==size) //若该位置的数不符合加1操作,则继续往左移一位 { position--; } vecOrder[position]++; //更新该位置的数,并更新其右边所有位置的数(依次为前面的数加1) for(int i=position;i<m-1;i++) { vecOrder[i+1]=vecOrder[i]+1; } for(int i=m-1;i>position;i--) //从最右向左检查position后面的数是否小于size,若有小于size的,则更新position为该数的位置,否则position大小不变 { if((i==m-1&&vecOrder[i]<size)||(i<m-1&&vecOrder[i]+1<vecOrder[i+1])) //需要判断是否是最右边的数 { position=i; break; } } } } return false; } int main() { int T,N,M,a,b,len,Start,End; cin>>T; vector<vector<string> >vecResult; //存放最终结果的容器 int coloumn,row=0; vector<vector<int> > vecAdjMatrix; vector<int> visited; //记录某点是否已经被访问过 vector<int> vecWeight; //记录从开始节点到目标节点的各个边的权值 while(T--) { vecAdjMatrix.clear(); visited.clear(); vecWeight.clear(); cin>>N; for(int i=0;i<N;i++) //初始化N*N的邻接矩阵,其元素值均为0 { vector<int> vecOneline(N); vecAdjMatrix.push_back(vecOneline); visited.push_back(0); //初始化访问数组值为0,表示没有被访问过 } for(int i=1;i<=N-1;i++) //根据输入构建邻接矩阵 { cin>>a>>b>>len; vecAdjMatrix[a-1][b-1]=len; vecAdjMatrix[b-1][a-1]=len; } cin>>M; //询问数 vector<string> vecOneCase; vecResult.push_back(vecOneCase); coloumn=0; while(M--) { cin>>Start>>End; hasFound=0; //初始化是否已经找到目标节点为:未找到 adj.clear(); //清空记录路径的map DFS(vecAdjMatrix,visited,N,Start,End); //深度优先遍历节点Start到节点End的路径 if(0==hasFound) { vecResult[row].push_back("No"); continue; } vecWeight.clear(); while(1) { vecWeight.push_back(vecAdjMatrix[Start-1][adj[Start]-1]); if(adj[Start]==End) { break; } Start=adj[Start]; } if(vecWeight.size()>=3) //至少要有3条边才能构成三角形 { int result=combination(vecWeight,vecWeight.size(),3); if(result) { vecResult[row].push_back("Yes"); } else { vecResult[row].push_back("No"); } } else { vecResult[row].push_back("No"); } coloumn++; } row++; } for(int i=0;i<vecResult.size();i++) { cout<<"Case #"<<i+1<<":"<<endl; for(int j=0;j<vecResult[i].size();j++) { cout<<vecResult[i][j]<<endl; } } return 0; }

  评论这张
 
阅读(289)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017