poj 2949 Word Rings (spfa+栈优化)
poj2949 题目链接 题意：我们有 n 个 (n<=100000) 字符串,每个字符串都是由 a~z 的小写英文字 母组成的字符串。如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两字符相 匹配,那么我们称 A 与 B 能相连(注意: A 能与 B 相连不代表 B 能与 A 相连)。 我们希望从给定的字符串中找出一些,使得他们首尾相接形成一个环串(一个串首尾相连也算) 我们想要使这个环串的平均长度最长。
思路：参考了国家集训队论文《spfa算法的优化与应用》
首先我卡在了关于接龙问题的处理方法，只能想到n^2的方法。。显然gg.
而正解是把每个单词看做一条边，把每个单词开头的两个字母和结尾两个字母看做起点和终点，由于都是小写字母，2位26进制数最多表示26*26。
这个建图方式并不是特别显然，不过想一下还是可以理解的。。以及这应该算是处理单词接龙问题的一个技巧。。。
这道题综合了两种常见的问题：字符串的接龙以及平均值的最优化问题。对于前者，我们可以采取把单词看成边，把首尾字母组合看成点的方法。例如对于单词ababc就是点”ab”向点”bc”连一条长度为5的边。这样问题的模型变得更加清晰，规模也得到减小。那么原问题就可以转化成在此图中找一个环，使得环上边权的平均值最大。对于这种问题，我们有很经典的解决方法：由于Average=(E1+E2+…..+Ek)/K 所以Average*K=E1+E2+……+Ek 即（E1-Average）+（E2-Average）+….+ （Ek-Average）=0 另外注意到上式中的等于号可以改写为小于等于，那么我们可以二分答案Ans，然后判断是否存在一组解满足（E1+E2+…..+Ek）/K>Ans,即判断 （E1- Ans）+（E2- Ans）+….+ （Ek- Ans）>0 于是在二分答案后，我们把边的权值更新，问题就变成了查找图中是否存在一个正环。
然后参考了这篇题解学习了一下栈优化的spfa： spfa栈优化
以及这篇博客中比较了dfs的spfa和普通栈优化的spfa… 200+ms vs 2000+ms…十倍的优化。。太神了。。。
/* 枚举每一个平均长度mid值。 如果存在一个环，(E1+...+Ek)/k>=mid(其中k是边数，E1……Ek是各个边权)， 那么正解比mid大，否则比mid小，这就是二分策略。 那么怎样知道是否存在(E1+...+Ek)/k>=mid 呢？ 如下转化：(E1+...+Ek)>=mid*k E1-mid + E2–mid + E3-mid + ... + Ek-mid >= 0 所以，把所有的边权改为Ei – mid，然后看是否存在正环就可以，存在就是满足条件。 */
1/* ***********************************************
2Author :111qqz
3Created Time :2016年05月25日 星期三 00时25分51秒
4File Name :code/poj/2949.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#include <stack>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E5+7;
35char st[1005];
36int f[900];
37bool ins[900];//是否在栈中
38double dis[900];
39int in[900]; //进栈次数，用来判断环。
40double maxedge; // d[i]>n*maxegde 可以认定必然有环。 这剪枝真的有效果。。？
41
42struct edge
43{
44 int v,nxt;
45 double w;
46}edge[N];
47int n;
48int tot;
49int cnt;//点的个数。
50int head[N];
51
52void addedge(int u,int v,double w)
53{
54 edge[tot].v = v;
55 edge[tot].w = w;
56 edge[tot].nxt = head[u];
57 head[u] = tot++;
58}
59
60bool spfa(double ave,int n)
61{
62
63 ms(in,0);
64 ms(ins,false);
65 ms(dis,0);
66 stack<int>S;
67 for ( int i = 1 ; i <= n ; i++) S.push(i),ins[i] = true;
68// cout<<"whhhhh?"<<endl;
69 while (!S.empty())
70 {
71 int u = S.top();
72// cout<<"u:"<<u<<endl;
73 S.pop();
74 ins[u]=false;
75
76 for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
77 {
78// cout<<"end of for?"<<endl;
79 int v = edge[i].v;
80 if (dis[v]<dis[u]+(edge[i].w-ave))
81 {
82 dis[v] = dis[u] + (edge[i].w-ave);
83 if (dis[v]>maxedge*n) return true;
84 if (ins[v]) continue;
85 ins[v] = true;
86 S.push(v);
87 in[v]++;
88 if (in[v]>n)
89 {
90 return true; //有环。
91 }
92 }
93 }
94 }
95
96 // cout<<"end of spfa:"<<endl;
97
98 return false;
99
100}
101
102void bin()
103{
104 double l = 0,r=1000,best=-1,mid;
105 while (l+0.001<=r)
106 {
107// cout<<"sadasd"<<endl;
108 mid = (l+r)/2;
109 if (spfa(mid,cnt))
110 {
111 best = mid;
112 l = mid;
113 }
114 else r = mid;
115 }
116 if (best!=-1) printf("%.2lf\n",best);
117 else puts("No solution.");
118}
119int main()
120{
121 #ifndef ONLINE_JUDGE
122 freopen("code/in.txt","r",stdin);
123 #endif
124
125 while (scanf("%d",&n)!=EOF)
126 {
127 if (n==0) break;
128 ms(f,0);
129 ms(head,-1); //总是忘记这个初始化....
130 cnt = 0;
131 tot = 0 ;
132 for ( int i = 1 ; i <= n ; i++)
133 {
134 scanf("%s",st);
135 int len = strlen(st);
136 if (len>maxedge)
137 {
138 maxedge = len;
139 }
140
141 int x = (st[0]-'a')*26 + st[1]-'a';
142 int y = (st[len-2]-'a')*26 + st[len-1]-'a';
143 if (f[x]==0) f[x] = ++cnt;
144 if (f[y]==0) f[y] = ++cnt;
145
146 int u = f[x];
147 int v = f[y];
148
149 addedge(u,v,double(len));
150 }
151
152
153 bin();
154 // cout<<"asdasd"<<endl;
155 }
156
157
158
159 #ifndef ONLINE_JUDGE
160 fclose(stdin);
161 #endif
162 return 0;
163}