时间限制: 5 Sec 内存限制: 256 MB Special Judge
题目描述
Bsny从字典挑出N个单词，并设计了接龙游戏，只要一个单词的最后两个字母和另一个单词的前两个字母相同，那么这两个单词就可以有序的连接起来。
Bsny想要知道在所给的所有单词中能否按照上述方式接龙组成一个单词环（可能是多个），若能，求所有环的环中单词平均长度最大值。
输入
第一行一个整数N，表示单词数量。
接下来N行，每行一个字符串，仅包含小写字母。
输出
若能组成单词环，输出环中单词的最大平均长度，结果保留2位小数；否则输出”No solution.”（不包括双引号）。精度误差在0.01都算正确。
样例输入
3
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
样例输出
21.67
提示
20%的数据：n≤20；
70%的数据：n≤1000；
100%的数据：n≤100000，每个单词长度不超过1000。输入数据比较大，C/C++的同学用scanf输入。
来源
NOIP2014八校联考Test2 Day2
Solution
这是一道不错的建图题，我们将一个字符串的首两个字母连向尾两个字母，长度为字符串长度。
如abcde即ab–>cd（长度为5)
然后我们枚举平均长度，现在我们将每条边的长度减去平均长度，跑一遍最长路，若找到了一个正权圈，即平均长度可以再大一些，否则就要小一些了。这样，我们可以二分这个平均长度，然后找到答案。若最终答案为0（在代码中为小于0.1，防止精度误差），则为”No solution.”。
若有两个字符串aaaaa和aaa，这样的情况也不用担心，自环应该是允许的，所以答案是5.00。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=100100,MAX=28*28; int n,tot,Max,p[N],Next[N],head[MAX],tree[N],num[MAX],x[MAX*2+3]; double val[N],dis[MAX]; bool vis[MAX]; void add(int x,int y,int z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } bool spfa(int s,double L) { int t=0,w=1;x[1]=s;dis[s]=0;vis[s]=1;num[s]=1; while (t!=w) { t++; if (t>MAX*2) t=1; int u=x[t]; vis[u]=false; for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (dis[v]<dis[u]+val[i]-L) { dis[v]=dis[u]+val[i]-L; if (!vis[s]) { w++; if (w>MAX*2) w=1; x[w]=v; vis[v]=true; num[v]++; if (num[v]>MAX) return true; } } } } return false; } bool check(double x) { for (int i=1;i<=Max;i++) vis[i]=0,dis[i]=-1LL<<31,num[i]=0; for (int i=1;i<=n;i++) { if (spfa(p[i],x)) return true; } return false; } int main() { scanf("%d",&n); tot=Max=0; for (int i=1;i<=n;i++) { char s[1005]; scanf("%s",s+1); int len=strlen(s+1); int x=(s[1]-96)*27+s[2]-96; int y=(s[len-1]-96)*27+s[len]-96; p[i]=x; Max=max(Max,max(x,y)); add(x,y,len); } double l=0,r=1000; while (r-l>1e-3) { double mid=(l+r)/2; if (check(mid)) l=mid;else r=mid; } if (l<0.1) printf("No solution.\n");else printf("%.2f\n",l); return 0; } |
自环不行吧，像这个http://blog.csdn.net/doyouseeman/article/details/54429506判了自环
感觉数据水而已
还有错别字 自环应该时允许的