给定 Infinity
。
一个十分精妙的图论。
关键的信息在
于是考虑如对于从
这样将图建完之后不难发现只需要 SPFA 跑一遍单源最长路,取最大的
于是点数为
当然这里我们用 map
实现,手动实现一个 hash()
之后用 unorderer_map
即可去掉 map
的
xxxxxxxxxx
1041
2
3
4
5
6
7
8
9
10
11using namespace std;
12
13mt19937 rnd(random_device{}());
14int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15bool rnddd(int x){return rndd(1, 100) <= x;}
16
17typedef unsigned int uint;
18typedef unsigned long long unll;
19typedef long long ll;
20typedef long double ld;
21
22
23
24template < typename T = int >
25inline T read(void);
26
27struct Edge{
28 Edge* nxt;
29 int to;
30 ll val;
31 OPNEW;
32}ed[21000];
33ROPNEW(ed);
34Edge* head[1100];
35
36int N;
37int cnt(0);
38unordered_map < string, int > score;
39map < pair < int, int >, int > mp;
40unordered_map < int, pair < int, int > > rmp;
41bitset < 1100 > inq;
42int dep[1100];
43ll dis[1100];
44ll ans(LONG_LONG_MIN);
45
46void SPFA(void){
47 memset(dis, 0xc0, sizeof dis);
48 queue < int > cur;
49 cur.push(1); inq[1] = true; dep[1] = 1, dis[1] = 0;
50 while(!cur.empty()){
51 int p = cur.front(); cur.pop();
52 inq[p] = false;
53 for(auto i = head[p]; i; i = i->nxt){
54 if(dis[p] + i->val > dis[SON]){
55 dis[SON] = dis[p] + i->val;
56 ans = max(ans, dis[SON]);
57 dep[SON] = dep[p] + 1;
58 if(dep[SON] > 26 * 26 + 26 + 1)printf("Infinity\n"), exit(0);
59 if(!inq[SON])cur.push(SON), inq[SON] = true;
60 }
61 }
62 }
63}
64
65int main(){
66 N = read();
67 for(int i = 1; i <= N; ++i){
68 string S; cin >> S;
69 score.insert({S, read()});
70 }mp.insert({{0, 0}, ++cnt}), rmp.insert({cnt, {0, 0}});
71 for(int i = 'a'; i <= 'z'; ++i)mp.insert({{0, i}, ++cnt}), rmp.insert({cnt, {0, i}});
72 for(int i = 'a'; i <= 'z'; ++i)for(int j = 'a'; j <= 'z'; ++j)
73 mp.insert({{i, j}, ++cnt}), rmp.insert({cnt, {i, j}});
74 for(int i = 1; i <= cnt; ++i)for(int j = 'a'; j <= 'z'; ++j){
75 ll tot(0); string S;
76 if(rmp[i].first)S += (char)rmp[i].first;
77 if(rmp[i].second)S += (char)rmp[i].second;
78 S += j; tot += score[S];
79 while(!S.empty()){
80 S.erase(S.begin());
81 tot += score[S];
82 }
83 head[i] = new Edge{head[i], mp[{rmp[i].second, j}], tot};
84 }SPFA();
85 printf("%lld\n", ans);
86 fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
87 return 0;
88}
89
90template < typename T >
91inline T read(void){
92 T ret(0);
93 int flag(1);
94 char c = getchar();
95 while(c != '-' && !isdigit(c))c = getchar();
96 if(c == '-')flag = -1, c = getchar();
97 while(isdigit(c)){
98 ret *= 10;
99 ret += int(c - '0');
100 c = getchar();
101 }
102 ret *= flag;
103 return ret;
104}
update-2023_01_03 初稿