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
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
char st[1005];
int f[900];
bool ins[900];//是否在栈中
double dis[900];
int in[900]; //进栈次数，用来判断环。
double maxedge; // d[i]>n*maxegde 可以认定必然有环。 这剪枝真的有效果。。？
struct edge
{
int v,nxt;
double w;
}edge[N];
int n;
int tot;
int cnt;//点的个数。
int head[N];
void addedge(int u,int v,double w)
{
edge[tot].v = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot++;
}
bool spfa(double ave,int n)
{
ms(in,0);
ms(ins,false);
ms(dis,0);
stack<int>S;
for ( int i = 1 ; i <= n ; i++) S.push(i),ins[i] = true;
// cout<<"whhhhh?"<<endl;
while (!S.empty())
{
int u = S.top();
// cout<<"u:"<<u<<endl;
S.pop();
ins[u]=false;
for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
{
// cout<<"end of for?"<<endl;
int v = edge[i].v;
if (dis[v]<dis[u]+(edge[i].w-ave))
{
dis[v] = dis[u] + (edge[i].w-ave);
if (dis[v]>maxedge*n) return true;
if (ins[v]) continue;
ins[v] = true;
S.push(v);
in[v]++;
if (in[v]>n)
{
return true; //有环。
}
}
}
}
// cout<<"end of spfa:"<<endl;
return false;
}
void bin()
{
double l = 0,r=1000,best=-1,mid;
while (l+0.001<=r)
{
// cout<<"sadasd"<<endl;
mid = (l+r)/2;
if (spfa(mid,cnt))
{
best = mid;
l = mid;
}
else r = mid;
}
if (best!=-1) printf("%.2lf\n",best);
else puts("No solution.");
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
while (scanf("%d",&n)!=EOF)
{
if (n==0) break;
ms(f,0);
ms(head,-1); //总是忘记这个初始化....
cnt = 0;
tot = 0 ;
for ( int i = 1 ; i <= n ; i++)
{
scanf("%s",st);
int len = strlen(st);
if (len>maxedge)
{
maxedge = len;
}
int x = (st[0]-'a')*26 + st[1]-'a';
int y = (st[len-2]-'a')*26 + st[len-1]-'a';
if (f[x]==0) f[x] = ++cnt;
if (f[y]==0) f[y] = ++cnt;
int u = f[x];
int v = f[y];
addedge(u,v,double(len));
}
bin();
// cout<<"asdasd"<<endl;
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}