Species Tree 利用HashTable实现实例代码
SpeciesTree利用HashTable实现
题目再现
题目内容：
给定一个物种演化图， 关系的表示方式如下： xy:表示x为y的先祖。 一个物种只会有一个先祖， 一个先祖可以有很多个演化出来的物种， 请你找出每个问题询问物种的祖父物种(先祖的先祖)， 每个物种会使用一个不重复的编号来表示， 如果该物种没有祖父物种的话或是不存在， 那么请将他的祖父物种当是0。(凭空而生) 保证所有物种间一定有所关连， 且不会有重复演化的现象发生， 即演化图只会是一棵树。 输入格式: 只有一组测资。 第一行会有两个数字N、Q，代表总共有N个物种及Q个问题。 接下来N-1行，每一行有两个数字x、y， 意义如题目所述。 接下来的Q行，每一行有一个数字Z， 代表要询问的物种编号。 测资范围： 1<N<10000 0<Q<1000 0<x,y,z<1000000 输出格式： 对于每一个询问的物种编号，将他们的祖父物种编号加总后再输出。 输入样例： 63 10002000 10003000 20004000 30005000 50006000 5000 6000 1234 输出样例： 4000 时间限制：100ms内存限制：16000kb
算法实现
1.简单数组下标查找法
通过题目的要求，这里可以使用最简单的方法，因为输入的x,y中，y的值是确定不变的，所以这里可以定义一个y的取值范围那么大的数组，下标就是y的值，内容就是x的值，这样查找起来十分方便，时间复杂度是O(1)，但是空间上就会浪费比较多了。
#include<stdio.h>
#include<string.h>
intmain(){
intarrBucket[1000000];
intN,Q;
intx,y,z;
longlongsum=0;
memset(arrBucket,0,sizeof(arrBucket));
scanf("%d%d",&N,&Q);
while(N-->1){
scanf("%d%d",&x,&y);
arrBucket[y]=x;
}
while(Q--){
scanf("%d",&z);
if(arrBucket[z]!=0){
if(arrBucket[arrBucket[z]]!=0){
sum+=arrBucket[arrBucket[z]];
}
}
}
printf("%lld",sum);
return0;
}
2.Hash表实现
因为方法1中，浪费空间严重，所以这里使用Hash表实现。
#include<stdio.h>
#include<stdlib.h>
#defineNULLKEY-1
typedefstruct{
int*elem;//元素
int*elemP;//父元素
intcount;
}HashTable;
intHash(HashTableH,intk){
returnk%H.count;
}
voidInitHashTable(HashTable*H){
inti;
H->elem=(int*)malloc(sizeof(int)*H->count);
H->elemP=(int*)malloc(sizeof(int)*H->count);
for(i=0;i<H->count;i++){
H->elem[i]=NULLKEY;
H->elemP[i]=NULLKEY;
}
}
voidInsertHash(HashTable*H,intkey,intvalue){
intaddr;
addr=Hash(*H,key);
while(H->elem[addr]!=NULLKEY){
addr=(addr+1)%H->count;
}
H->elem[addr]=key;
H->elemP[addr]=value;
}
intFindHash(HashTable*H,intkey,int*addr){
*addr=Hash(*H,key);
while(H->elem[*addr]!=key){
*addr=(*addr+1)%H->count;
if(H->elem[*addr]==NULLKEY||*addr==Hash(*H,key)){
return0;
}
}
return1;
}
intmain(){
intN,Q;
intx,y,z,addr;
longlongsum=0;
HashTableH;
scanf("%d%d",&N,&Q);
H.count=N-1;
InitHashTable(&H);
while(N-->1){
scanf("%d%d",&x,&y);
InsertHash(&H,y,x);
}
while(Q--){
scanf("%d",&z);
if(FindHash(&H,z,&addr)){
if(FindHash(&H,H.elemP[addr],&addr)){
sum+=H.elemP[addr];
}
}
}
printf("%lld",sum);
return0;
}
3.用C++的map来实现
看着用C实现起来，相对来说实现的各个功能都要自己写，这里看一下用C++的STL里面的map来实现上面的题目，非常简单（不得不说STL真的很好用，但是不如HashTable速度快，空间上也不如HashTable占用的小）
#include<iostream>
#include<map>
usingnamespacestd;
intmain(){
intn,q;
cin>>n>>q;
map<int,int>mp;
map<int,int>::iteratorit;
intx,y,z;
for(inti=1;i<n;++i){
cin>>x>>y;
mp.insert(pair<int,int>(y,x));
}
intsum=0;
for(inti=0;i<q;++i){
cin>>z;
it=mp.find(z);
if(it!=mp.end()){
it=mp.find(it->second);
if(it!=mp.end())
sum+=it->second;
}
}
cout<<sum;
return0;
}
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！