题目链接
分析： 这道题很好理解，如果B要求A实现，那么就从A连一条有向边到B，然后在DAG上跑一个带星的最长路。 只是这个输入非常反人类啊，难点在输入上＝ ＝
代码：
#include <iostream> #include <map> #include <vector> #include <queue> #include <cstring> using namespace std; const int maxn = 1e3 + 5; bool tag[maxn]; string t[maxn]; map<string, int> mp; vector<int> G[maxn]; int cnt; int ind[maxn]; int d[maxn]; void mark(string s) { int len = (int)s.length(); int i; bool flag = false; string tmp = ""; for (i = 0; i < len; i ++) { if (s[i] == '*') flag = true; if (s[i] == '*' || s[i] == ':') break; tmp = tmp + s[i]; } if (flag) tag[cnt] = true; t[cnt] = s.substr(i + flag + 1, len); // cout<<t[cnt]<<endl; mp[tmp] = cnt ++; } void addedge(string t, int v) { string tmp = ""; int len = (int)t.length(); for (int i = 0; i < len; i ++) { if (t[i] == ' ') { if (tmp.length() > 0) { int u = mp[tmp]; G[u].push_back(v); ind[v] ++; // cout<<tmp<<" "<<v<<endl; } tmp = ""; } else tmp = tmp + t[i]; } if (tmp.length() > 0) { int u = mp[tmp]; G[u].push_back(v); ind[v] ++; // cout<<tmp<<" "<<v<<endl; } tmp = ""; } int calc() { memset(d, 0, sizeof(d)); queue<int > q; for (int i = 0; i < cnt; i ++) if (ind[i] == 0) { q.push(i); d[i] = tag[i]; } int ans = 0; while (!q.empty()) { int u = q.front(); q.pop(); ans = max(ans, d[u]); for (int v : G[u]) { ind[v] --; d[v] = max(d[v], d[u] + tag[v]); if (ind[v] == 0) q.push(v); } } return ans; } void print() { for (int i = 0; i < cnt; i ++) for (int v : G[i]) cout<<i<<" "<<v<<endl; } int main(int argc, char const *argv[]) { int T; cin>>T; int kase = 1; getchar(); getchar(); while (T --) { memset(tag, false, sizeof(tag)); memset(ind, 0, sizeof(ind)); for (int i = 0; i <= 1e3; i ++) G[i].clear(); mp.clear(); cnt = 0; string s; while (getline(cin, s)) { if (s.length() == 0) break; mark(s); } for (int i = 0; i < cnt; i ++) addedge(t[i], i); // print(); printf("Case %d: %d\n", kase ++, calc()); } return 0; }