题目链接:Codeforces/Vjudge
题目大意:在object oriented programming 语言中的类之间存在两种关系 is-a,has-a,分别为子类与包含关系。给出若干初始条件,然后进行若干询问(A是否是B的子类或A是否包含B), 请回答询问是否真。
is-a关系具有传递性,所以可以通过解传递闭包的方法来做这个题目。如果从A到C存在一条全部由is-a关系构成的道路, 那么A is-a C。如果连接AC的道路中间存在某个has-a关系,则从这个has-a关系之后的所有关系都应该变为has-a。
需要注意的坑就是两个类之间也许不只有一种关系,所以is和has需要分开。
Floyd算法的AC代码:
#include <iostream> #include <string> #include <map> using namespace std; const int MAXN = (int) 5e2 + 5; bool is[MAXN][MAXN]; bool has[MAXN][MAXN]; bool rel[MAXN][MAXN][2]; inline void init() { fill(&is[0][0], &is[0][0] + MAXN * MAXN, false); fill(&has[0][0], &has[0][0] + MAXN * MAXN, false); fill(&rel[0][0][0], &rel[0][0][0] + MAXN * MAXN * 2, false); for (int i = 0; i < MAXN; ++i) { is[i][i] = true; } } inline void floyd(int upbound) { for (int i = 0; i < upbound; ++i) { for (int j = 0; j < upbound; ++j) { if (is[i][j])rel[i][j][1] = true; if (has[i][j])rel[i][j][0] = true; } } for (int k = 0; k < upbound; ++k) { for (int i = 0; i < upbound; ++i) { for (int j = 0; j < upbound; ++j) { if (rel[i][k][1] && rel[k][j][1])rel[i][j][1] = true; if ((rel[i][k][1] && rel[k][j][0]) || (rel[i][k][0] && rel[k][j][1]) || (rel[i][k][0] && rel[k][j][0])) rel[i][j][0] = true; } } } } int class_flag = -1; map<string, int> class_cnt; inline int cls(const string &s) { map<string, int>::iterator it; if ((it = class_cnt.find(s)) != class_cnt.end())return it->second; else { class_cnt.insert(make_pair(s, ++class_flag)); return class_flag; } } int main() { init(); int n, m; scanf("%d%d", &n, &m); string c1, r, c2; for (int i = 0; i < n; ++i) { cin >> c1 >> r >> c2; if (r[0] == 'i') { is[cls(c1)][cls(c2)] = true; } else { has[cls(c1)][cls(c2)] = true; } } floyd(class_flag + 1); for (int i = 1; i <= m; ++i) { cin >> c1 >> r >> c2; int tp = r[0] == 'i' ? 1 : 0; printf("Query %d: %s\n", i, rel[cls(c1)][cls(c2)][tp] ? "true" : "false"); } return 0; }
DFS的AC代码:
#include <iostream> #include <string> #include <map> using namespace std; const int MAXN = (int) 1e3 + 5; bool is[MAXN][MAXN]; bool has[MAXN][MAXN]; bool ins[MAXN][MAXN][2]; inline void init() { fill(&is[0][0], &is[0][0] + MAXN * MAXN, false); fill(&has[0][0], &has[0][0] + MAXN * MAXN, false); fill(&ins[0][0][0], &ins[0][0][0] + MAXN * MAXN * 2, false); for (int i = 0; i < MAXN; ++i) { is[i][i] = true; } } int class_flag = -1; map<string, int> class_cnt; inline int cls(const string &s) { map<string, int>::iterator it; if ((it = class_cnt.find(s)) != class_cnt.end())return it->second; else { class_cnt.insert(make_pair(s, ++class_flag)); return class_flag; } } void dfs(int root, int cur, int cur_type) { for (int i = 0; i < MAXN; ++i) { if (!ins[root][i][cur_type] && is[cur][i]) { ins[root][i][cur_type] = true; dfs(root, i, cur_type); } if (!ins[root][i][0] && has[cur][i]) { ins[root][i][0] = true; dfs(root, i, 0); } } } int main() { init(); int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) { string c1, r, c2; cin >> c1 >> r >> c2; if (r[0] == 'i') { is[cls(c1)][cls(c2)] = true; } else { has[cls(c1)][cls(c2)] = true; } } for (int i = 0; i <= class_flag; ++i) { dfs(i, i, 1); } for (int i = 1; i <= m; ++i) { string c1, r, c2; cin >> c1 >> r >> c2; int tp = r == "is-a" ? 1 : 0; printf("Query %d: %s\n", i, ins[cls(c1)][cls(c2)][tp] ? "true" : "false"); } return 0; }
网上能找到的别的题解都是BFS的,这里就不写了。
Comments | NOTHING