考察:01分数规划+SPFA判环
思路:
和之前的最小环没什么区别,本题最难在建边.看题目很想当然的是二重for循环字符串建边,但是明显会TLE并且MLE,
考虑换一个思路, ababc + bckjaca -> aba bc kjaca 只考虑前面两个与结尾两个,就转化为 ab-> bc->ca即将字符串化为边.这样点最多26*26个,边最多105 个.
最后就是SPFA+玄学优化.
注意n是边的数量.
1 #include <iostream>
2 #include <cstring>
3 #include <queue>
4 #include <map>
5 using namespace std;
6 const double eps = 1e-6;
7 const int N = 680,M = 100010,S = 1010;
8 int n,id,idx,h[N],cnt[N];
9 map<int,int> mp;
10 bool st[N];
11 double dist[N];
12 char s[S];
13 struct Road{
14 int fr,to,ne,w;
15 }road[M];
16 void add(int a,int b,int w)
17 {
18 road[idx].w = w,road[idx].fr = a,road[idx].to = b,road[idx].ne =h[a],h[a] = idx++;
19 }
20 int get(int x)
21 {
22 if(!mp.count(x)) mp[x] = ++id;
23 return mp[x];
24 }
25 bool check(double mid)
26 {
27 queue<int> q;
28 int count = 0;
29 for(int i=1;i<=id;i++) dist[i] = 0,cnt[i] = 0,q.push(i),st[i] = 1;
30 while(q.size())
31 {
32 int u = q.front();
33 q.pop();
34 st[u] = 0;
35 for(int i=h[u];~i;i=road[i].ne)
36 {
37 int v = road[i].to;
38 if(dist[v]<dist[u]+road[i].w - mid)
39 {
40 dist[v] = dist[u]+road[i].w - mid;
41 cnt[v] = cnt[u]+1,count++;
42 if(count>=4*id) return 1;
43 if(cnt[v]>=id) return 1;
44 if(!st[v]) q.push(v),st[v] = 1;
45 }
46 }
47 }
48 return 0;
49 }
50 int main()
51 {
52 while(scanf("%d",&n)!=EOF&&n)
53 {
54 idx = 0;
55 id = 0; mp.clear();
56 for(int i=1;i<=N-4;i++) h[i] = -1;
57 for(int i=1;i<=n;i++)
58 {
59 scanf("%s",s);
60 int len = strlen(s);
61 int a = (s[0]-'a'+1)*26+(s[1]-'a'+1);
62 int b = (s[len-2]-'a'+1)*26+(s[len-1]-'a'+1);
63 int fr = get(a); int to = get(b);
64 add(fr,to,len);
65 }
66 double l = 0,r = 1010;
67 while(r-l>=eps)
68 {
69 double mid = (l+r)/2;
70 if(check(mid)) l = mid;
71 else r = mid;
72 }
73 if(r>=eps) printf("%.2lf\n",r);
74 else puts("No solution");
75 }
76 return 0;
77 }