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，然后看是否存在正环就可以，存在就是满足条件。 */
/* ***********************************************
Author :111qqz
Created Time :2016年05月25日 星期三 00时25分51秒
File Name :code/poj/2949.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#include <stack>
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7char st[1005];
8int f[900];
9bool ins[900];//是否在栈中
10double dis[900];
11int in[900]; //进栈次数，用来判断环。
12double maxedge; // d[i]>n*maxegde 可以认定必然有环。 这剪枝真的有效果。。？
1struct edge
2{
3 int v,nxt;
4 double w;
5}edge[N];
6int n;
7int tot;
8int cnt;//点的个数。
9int head[N];
1void addedge(int u,int v,double w)
2{
3 edge[tot].v = v;
4 edge[tot].w = w;
5 edge[tot].nxt = head[u];
6 head[u] = tot++;
7}
bool spfa(double ave,int n)
{
1 ms(in,0);
2 ms(ins,false);
3 ms(dis,0);
4 stack<int>S;
5 for ( int i = 1 ; i <= n ; i++) S.push(i),ins[i] = true;
6// cout<<"whhhhh?"<<endl;
7 while (!S.empty())
8 {
9 int u = S.top();
10// cout<<"u:"<<u<<endl;
11 S.pop();
12 ins[u]=false;
1 for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
2 {
3// cout<<"end of for?"<<endl;
4 int v = edge[i].v;
5 if (dis[v]<dis[u]+(edge[i].w-ave))
6 {
7 dis[v] = dis[u] + (edge[i].w-ave);
8 if (dis[v]>maxedge*n) return true;
9 if (ins[v]) continue;
10 ins[v] = true;
11 S.push(v);
12 in[v]++;
13 if (in[v]>n)
14 {
15 return true; //有环。
16 }
17 }
18 }
19 }
// cout<<"end of spfa:"<<endl;
return false;
}
1void bin()
2{
3 double l = 0,r=1000,best=-1,mid;
4 while (l+0.001<=r)
5 {
6// cout<<"sadasd"<<endl;
7 mid = (l+r)/2;
8 if (spfa(mid,cnt))
9 {
10 best = mid;
11 l = mid;
12 }
13 else r = mid;
14 }
15 if (best!=-1) printf("%.2lf\n",best);
16 else puts("No solution.");
17}
18int main()
19{
20 #ifndef ONLINE_JUDGE
21 freopen("code/in.txt","r",stdin);
22 #endif
1 while (scanf("%d",&n)!=EOF)
2 {
3 if (n==0) break;
4 ms(f,0);
5 ms(head,-1); //总是忘记这个初始化....
6 cnt = 0;
7 tot = 0 ;
8 for ( int i = 1 ; i <= n ; i++)
9 {
10 scanf("%s",st);
11 int len = strlen(st);
12 if (len>maxedge)
13 {
14 maxedge = len;
15 }
1 int x = (st[0]-'a')*26 + st[1]-'a';
2 int y = (st[len-2]-'a')*26 + st[len-1]-'a';
3 if (f[x]==0) f[x] = ++cnt;
4 if (f[y]==0) f[y] = ++cnt;
int u = f[x];
int v = f[y];
addedge(u,v,double(len));
}
1 bin();
2 // cout<<"asdasd"<<endl;
3 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}