Species Tree 利用HashTable实现

题目再现

题目内容：

给定一个物种演化图，关系的表示方式如下：x y : 表示x为y的先祖。一个物种只会有一个先祖，一个先祖可以有很多个演化出来的物种，请你找出每个问题询问物种的祖父物种(先祖的先祖)，每个物种会使用一个不重复的编号来表示，如果该物种没有祖父物种的话或是不存在，那么请将他的祖父物种当是0。(凭空而生)保证所有物种间一定有所关连，且不会有重复演化的现象发生，即演化图只会是一棵树。输入格式:只有一组测资。第一行会有两个数字N、Q，代表总共有N个物种及Q个问题。接下来N-1行，每一行有两个数字x、y，意义如题目所述。接下来的Q行，每一行有一个数字Z，代表要询问的物种编号。测资范围：1 < N < 100000 < Q < 10000 < x, y, z < 1000000输出格式：对于每一个询问的物种编号，将他们的祖父物种编号加总后再输出。输入样例：6 31000 20001000 30002000 40003000 50005000 6000500060001234输出样例：4000时间限制：100ms内存限制：16000kb

算法实现

1. 简单数组下标查找法

通过题目的要求，这里可以使用最简单的方法，因为输入的x , y中，y的值是确定不变的，所以这里可以定义一个y的取值范围那么大的数组，下标就是y的值，内容就是x的值，这样查找起来十分方便，时间复杂度是O(1)，但是空间上就会浪费比较多了。

#include <stdio.h>#include <string.h>int main(){ int arrBucket[1000000]; int N, Q; int x, y, z; long long sum = 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); return 0;}

2. Hash表实现

因为方法1中，浪费空间严重，所以这里使用Hash表实现。

#include <stdio.h>#include <stdlib.h>#define NULLKEY -1typedef struct { int *elem; //元素 int *elemP; //父元素 int count;}HashTable;int Hash(HashTable H, int k){ return k % H.count;}void InitHashTable(HashTable *H){ int i; 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; }}void InsertHash(HashTable *H, int key, int value){ int addr; addr = Hash(*H, key); while(H->elem[addr] != NULLKEY){ addr = (addr + 1) % H->count; } H->elem[addr] = key; H->elemP[addr] = value;}int FindHash(HashTable *H, int key, 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)){ return 0; } } return 1;}int main(){ int N, Q; int x, y, z, addr; long long sum = 0; HashTable H; 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); return 0;}

3. 用C++的map来实现

看着用C实现起来，相对来说实现的各个功能都要自己写，这里看一下用C++的STL里面的map来实现上面的题目，非常简单（不得不说STL真的很好用，但是不如HashTable速度快，空间上也不如HashTable占用的小）

#include <iostream>#include <map>using namespace std;int main() { int n, q; cin >> n >> q; map<int,int> mp; map<int,int>::iterator it; int x, y, z; for (int i=1; i<n; ++i) { cin >> x >> y; mp.insert(pair<int,int>(y,x)); } int sum = 0; for (int i=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; return 0;}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！