集训队作业-rings解题报告

《WordRings》解题报【题目来ACM/ICPCCentralEuropeanRegionalContest【题目描【输入格【输出格平均长度。输出保留两位小数。如果不能构造出单词环，输出”Nosolution.”【输入样3【输出样【题目分边数为100000，这个规模已经了。接下来要考虑如何寻找平均权值最大的回路。设ci表示边ix1,x2,…,xm在{0,1}中取值，xi=1当且仅当边i出现在回路中。的任

mmrmm，这个问题直接解决比价考虑对于一个确定的r值r0，将上式变， p(r0xicir0xixidi(dicir0opt(r0) 大值，则opt(r0)等于以di的最优解向量代入opt(r0’)的表达式可以得到一个更大的p值，即opt(r0)>0r0<r*opt(r0)=0r0=r*opt(r0)<0当且仅当r0>r*r0opt(r0)=0r0r*。那么如何求s0SPFAs顶点的最长路径。当队列达到预定的最大值时如果SPFA算法仍然没有结束，那分析算法的时间复杂度，SPFA算法的时间复杂度是OEn2626)设图中边的最小权值是wmin，最大权值是wmax，输出要求的精度为prec用SPFA算法的次数O((n2626)wmaxwmin

wmaxwmin

【性能分【总结【致谢programword;constvarn,maxta,he,ta:longint;g:array[1..maxr]oftnode;al:array[1..maxr]ofboolean;q:array[0..maxq-1]oflongint;d:array[1..maxr]ofre;vari:longint;fori:=1tomaxrwhileg[i]<>nildobeginprocedurebuild(varq:tnode;no,c:longint);{qvartq:tnode;vari,f,l:longint;fori:=1tondobeginiflength(s)<lethenle:=length(s);iflength(s)>rithenvari:longint;fori:=1tomaxrdobeginal[q[heand(maxq-te:=g[q[heand(maxq-1)]];whilete<>nildobeginifd[q[heand(maxq-1)]]+te^.c-now>d[te^.no]

d[te^.no]:=d[q[heand(maxq-1)]]+te^.c-now;ifnotal[te^.no]thenbeginq[taand(maxq-1)]:=te^.no;ifta>=maxtathenbeginmaxta:=(maxr+n)*2;{SPFA队列的最大值whileabs(le-ri)>1e-3dobegin{二分枚举}ifokthenifnow>otheno:=now;endelseri:=now;ifo>0thenwri n(o:0:2)elsewri ifn=0thenbreak;【英文原WordAwordringisasequenceofwordswherethelasttwolettersofeachwordarethesameasthetwolettersofthenextword(andthelasttwolettersofthelastwordarethesameasthetwolettersoftheword).Forexample,thefollowingsequenceisawordring:Yourtaskistowriteaprogramthat,givenalistofwords,findsawordring.Youhavetomakethewordringasimpressiveaspossible:theaveragelengthofthewordsintheringhastobeaslargeaspossible.Intheaboveexample,theaveragelengthis(20+21+24)/3≈21.6666,withmakesitsomewhatimpressive.Notethateachwordcanbeusedatmostonceinthering,andtheringcanconsistofasingleword.Theinputcontainsseveralblocksoftestcases.Eachcasebeginswithalinecontainingasingleinteger1≤n≤100000,thenumberofpossiblewordsthatcanbeused.Thenextnlinescontainthesewords.TheinputisterminatedbyablockwithForeachtestcaseintheninput,youhavetooutputasinglenumberonaseparaine:thenumaveragelengthofaringcomposedfrom(asubsetof)thewordsgivenintheinput.Theaveragelengthshouldbepresentedasareal