《WordRings》解題報【題目來ACM/ICPCCentralEuropeanRegionalContest【題目描【輸入格【輸出格平均長度。輸出保留兩位小數(shù)。如果不能構造出單詞環(huán)，輸出”Nosolution.”【輸入樣3【輸出樣【題目分邊數(shù)為100000，這個規(guī)模已經(jīng)了。接下來要考慮如何尋找平均權值最大的回路。設ci表示邊ix1,x2,…,xm在{0,1}中取值，xi=1當且僅當邊i出現(xiàn)在回路中。的任

mmrmm，這個問題直接解決比價考慮對于一個確定的r值r0，將上式變， p(r0xicir0xixidi(dicir0opt(r0) 大值，則opt(r0)等于以di的最優(yōu)解向量代入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算法的次數(shù)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