Description

Bsny從字典挑出N個單詞，并設計了接龍游戲，只要一個單詞的最后兩個字母和另一個單詞的前兩個字母相同，那么這兩個單詞就可以有序的連接起來。
Bsny想要知道在所給的所有單詞中能否按照上述方式接龍組成一個單詞環（可能是多個），若能，求所有環的環中單詞平均長度最大值。

Input

第一行一個整數N，表示單詞數量。
接下來N行，每行一個字符串，僅包含小寫字母。

Output

若能組成單詞環，輸出環中單詞的最大平均長度，結果保留2位小數；否則輸出”No solution.”（不包括雙引號）。精度誤差在0.01都算正確。

Sample Input

3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein

Sample Output

21.67

Data Constraint

20%的數據：n≤20；
70%的數據：n≤1000；
100%的數據：n≤100000，每個單詞長度不超過1000。輸入數據比較大，C/C++的同學用scanf輸入。

Solution

• 把問題轉換一下，可以這樣處理：

• 把一個單詞的前兩個單詞和后兩個單詞視為點，單詞長度視為邊權

• 那么點數最多為 26?26=676 個點，這樣在其中找環即可

• 看到題目問的是最大值，那么可以二分答案 len，每一條邊權值減去 len，

• 于是問題變成判定是否存在正權環！有則 len 可以更大，沒有則更小。

• 對于判定環，可以使用 SPFA，BFS和DFS都可以，每個點跑一次最長路即可

• 詳情請見我的博客：http://blog.csdn.net/liyizhixl/article/details/54565085

• （SPFA算法及判負環方法）

• 注意走過的點不用再做SPFA，時間復雜度 O(NlogN)

Code

#include<cstdio> #include<cstring> using namespace std; const int N=3000001,M=26*26+1; const double E=1e-3; int n,tot; int node[M],que[N]; double dis[M],w[N]; int first[M],next[N],en[N]; bool bz[M],vis[M]; char s[1002]; inline int get(int x,int y) {return 26*(x-'a')+y-'a'+1; } inline void insert(int x,int y,int z) {next[++tot]=first[x];first[x]=tot;en[tot]=y;w[tot]=z; } inline bool spfa(int st,double num) {for(int i=1;i<=node[i];i++) dis[node[i]]=0;int l=0,r=1;vis[que[1]=st]=true;while(l<r){int now=que[++l];bz[now]=false;for(int i=first[now];i;i=next[i])if(dis[now]+w[i]-num>dis[en[i]]){dis[en[i]]=dis[now]+w[i]-num;if(!bz[en[i]]){bz[que[++r]=en[i]]=vis[en[i]]=true;if(r>n) return true;}}}return false; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s+1);int len=strlen(s+1);if(len==1) continue;int x=get(s[1],s[2]),y=get(s[len-1],s[len]);if(x!=y) insert(x,y,len);if(!vis[x]) vis[node[++node[0]]=x]=true;if(!vis[y]) vis[node[++node[0]]=y]=true;}double l=0,r=1000;while(l+E<r){double mid=(l+r)/2;for(int i=1;i<=node[0];i++) vis[node[i]]=false;bool pd=false;for(int i=1;i<=node[0];i++)if(!vis[node[i]] && spfa(node[i],mid)){pd=true;break;}if(pd) l=mid; else r=mid;}if(!l) printf("No solution."); else printf("%.2lf",l);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 3852. 【NOIP2014八校联考第2场第2试9.28】单词接龙(words)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。