|
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 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#include <iostream> #include <sstream> #include <string> #include <queue> #include <cstdio> #define INF 10000000 using namespace std; bool gr[26][26]; int daysreq[26],indegree[26]; int accumulated_days[26]; int t; int bfs(queue<int> q) { while(!q.empty()) { int a = q.front();q.pop(); for(int i=0;i<26;i++) { if(gr[a][i]) { accumulated_days[i]=max(accumulated_days[i],accumulated_days[a]+daysreq[i]); if(--indegree[i]==0) q.push(i); } } } int MX = 0; for(int i=0;i<26;i++) { MX = max(accumulated_days[i],MX); } cout<<MX<<"\n"; if(t) cout<<"\n"; return 0; } int main() { string s; stringstream ss; getline(cin,s); ss<<s; ss>>t; getline(cin,s); ss.clear(); while(t--) { for(int i=0;i<26;i++) { daysreq[i]=0; indegree[i]=0; accumulated_days[i]=0; for(int j=0;j<26;j++) gr[i][j]=0; } while(getline(cin,s) && s!="") { ss<<s; char c; int d,u; ss>>c>>d; u = c-'A'; daysreq[u]=d; while(ss>>c) { gr[c-'A'][u]=1; } ss.clear(); } for(int i=0;i<26;i++) { for(int j=0;j<26;j++) { if(gr[i][j]) indegree[j]++; } } queue<int> q; for(int i=0;i<26;i++) { if(daysreq[i]!=0 && indegree[i]==0) { accumulated_days[i]=daysreq[i]; q.push(i); } } bfs(q); } return 0; } |