POJ2021 Relative Relatives

发表于 分类于

这题用到了 STL 的强大功能，简单图论，但是需要进行 hash，我运用的是 map 来 hash。

首先是建图，将父子关系连有向边，从父亲到孩子，这样我们就可以通过 DFS 一遍找到全部的年龄。注意 map 的定义。最后用一个 rbt 来维护最后的解有序，当然，你也可以运用向量 vector 来维护，总的时间复杂度是 O(nlgn)O(nlgn) 的。

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>

using namespace std;

struct Ans {
  string name;
  int age;
  bool operator<(const Ans& ans) const {
    if (age != ans.age)
      return age > ans.age;
    else
      return name < ans.name;
  }
};

map<string, int> age;
map<string, map<string, int> > mp;
set<Ans> st;

void dfs(string name) {
  map<string, int>::iterator it;
  for (it = mp[name].begin(); it != mp[name].end(); it++) {
    if (!age[(*it).first]) {
      age[(*it).first] = age[name] - (*it).second;
      dfs((*it).first);
    }
  }
}

int main() {
  int t, cnt = 0, n, num;
  string a, b;
  char s[120];
  map<string, int>::iterator it;
  set<Ans>::iterator iter;
  Ans ans;
  scanf("%d", &t);
  while (t--) {
    cnt++;
    mp.clear();
    age.clear();
    age["Ted"] = 100;
    scanf("%d", &n);
    while (n--) {
      scanf("%s", s);
      a = s;
      scanf("%s", s);
      b = s;
      scanf("%d", &num);
      mp[a][b] = num;
    }
    dfs("Ted");
    st.clear();
    for (it = age.begin(); it != age.end(); it++) {
      ans.name = (*it).first;
      ans.age = (*it).second;
      st.insert(ans);
    }
    printf("DATASET %d\n", cnt);
    for (iter = st.begin(); iter != st.end(); iter++) {
      if ((*iter).name == "Ted") continue;
      printf("%s %d\n", (*iter).name.c_str(), (*iter).age);
    }
  }
  return 0;
}