第二次作業(yè)解題報(bào)告-spoj

1、IOI2009by Jia Zhihao from No.2 Middle School in Shijiazh uang_spoj1674解題石家莊二中 賈Jia Zhihao From No.2 Midd le School,In Shijizhuang, Of Hebei Province題目大意設(shè)圖 G 有 N 個(gè)點(diǎn)，每個(gè)點(diǎn)恰好向外連一條有向邊，現(xiàn)在讓你找出最小的點(diǎn)集S，使得對(duì)于任何不屬于 S 的點(diǎn)，有向邊一定連向?qū)儆?S 的點(diǎn)。解題方法首先， 以單獨(dú)考慮每可以發(fā)現(xiàn)，有向圖的連通分支之間是相互沒(méi)有影響的，所以通分支?？蓪?duì)于每通分支，它的結(jié)構(gòu)都大致如下圖。可以只要將圖中的環(huán)上刪去一個(gè)點(diǎn)，

2、那么原圖就變成了一棵樹(shù)，且每個(gè)點(diǎn)的有向邊恰好連向他的父節(jié)點(diǎn)。于是不難想到：可以將圖轉(zhuǎn)化成樹(shù)形 DP 來(lái)做。第 1 頁(yè) 共 8 頁(yè)IOI2009by Jia Zhihao from No.2 Middle School in Shijiazh uang方法如下：對(duì)于每通分支，任意找環(huán)上的一條邊，則他兩端的點(diǎn)至少有一個(gè)在S 中，枚哪個(gè)點(diǎn)在 S 中，之后可以去掉枚舉的點(diǎn)向外連的有向邊，該連通分支轉(zhuǎn)化成了樹(shù)。下面兩幅圖為兩種情況。對(duì)于每一種情況，用樹(shù)形 DP 計(jì)算|S|的最小值。子-右兄弟的二叉表示法表示，用lch(v) 表示v 的先將多叉樹(shù)用子， rch(v) 表示 v 的右兒子。定義dp(v,0)

3、 表示v 的父親節(jié)點(diǎn)屬于 S 時(shí)， v 在二叉表示的子樹(shù)中，最少有幾個(gè)節(jié)點(diǎn)屬于 S；定義dp(v,1) 表示 v 的父親節(jié)點(diǎn)不屬于 S 時(shí)， v 在二叉表示的子樹(shù)中，最少有幾個(gè)節(jié)點(diǎn)屬于 S；則dp(lch(v),0) dp(rch(v),0) 1dp(lch(v),1) dp(rch(v),0)dp(v,0) min dp(lch(v),0) dp(rch(v),1) 1dp(lch(v),1) dp(rch(v),1)dp(v,1) dp(lch(v),0) dp(rch(v),1) 1dp(0,0) 0dp(0,1) 0特別的，于是，可以通過(guò)這個(gè)方法求出每通分支的 min|S|，相加起來(lái)就

4、是最終。總結(jié)第 2 頁(yè) 共 8 頁(yè)IOI2009by Jia Zhihao from No.2 Middle School in Shijiazh uang要發(fā)現(xiàn)題目的特點(diǎn)：圖 G 有 N 個(gè)點(diǎn)，每個(gè)點(diǎn)恰好向外連一條有向邊，則圖 G 的每通分支有且僅有一個(gè)環(huán)。多叉樹(shù)的子-右兄弟的二叉表示法。用 DP解決樹(shù)。附代碼第 3 頁(yè) 共 8 頁(yè)IOI2009by Jia Zhihao from No.2 Middle School in Shijiazh uang第 4 頁(yè) 共 8 頁(yè)P(yáng)ROGRAM spoj; CONSTmaxnum=60000000; VARlast,pre,next,fa,lch,

5、rch:array1.100000of long; d:array0.100000,0.1of long; c:array0.100000of record x,y:long;end; k1,k2,ans,i,numtest,test,n,m:long;Function find(v:long):long;Beginwhile favfafav do fav:=fafav; exit(fav);End;Procedure build(root:long);Vari:long;Begini:=lastfind(root); while i0 do beginlchi:=0;rchi:=0; di

6、,0:=-1;di,1:=-1;i:=prei; end;whilei:=lastfind(root); while i0 do beginif iroot then beginif lchnexti=0 then lchnexti:=i else beginrchi:=lchnexti;lchnexti:=i; end;elseend; i:=prei;IOI2009by Jia Zhihao from No.2 Middle School in Shijiazh uang第 5 頁(yè) 共 8 頁(yè)end;while End;Function dp(v,c:long):long;Vari,k1,

7、k2:long;Beginif dv,c-1 then dp:=dv,c else if v=0 then dp:=0else begin dv,c:=maxnum;if(c=0)then dv,c:=dp(lchv,1)+dp(rchv,0)+1 else beginif dp(rchv,0)dp(rchv,1) then k1:=dp(rchv,0) else k1:=dp(rchv,1);if dp(lchv,0)dp(lchv,1)+1 then k2:=dp(lchv,0) else k2:=dp(lchv,1)+1;dv,c:=k1+k2; end;else dp:=dv,c;en

8、d;else End;BEGINread(numtest);for test:=1 to numtest do begin read(n);m:=0;for i:=1 to n do fai:=i; fillchar(last,sizeof(last),0); for i:=1 to n do beginread(nexti);if find(i)find(nexti) then fafind(i):=find(nexti) else begininc(m);cm.x:=i;cm.y:=nexti; end;elseend;for iIOI2009by Jia Zhihao from No.2

9、 Middle School in Shijiazh uang附英文原題SPOJ Problem Set (classical)1674. The ExploProblem code: EXPLOSNegabyand began calm and quietly as any other day. Some people wentThe day of 6.XII.2003to work, some - to school, some - to store to buy food. Drivers were traditionally stuckedrafficjams, drinking co

10、ffee and reading morning newspr. Suddenly the regularity of this day wasdisturbed by huge explo began to run away in panic.They blew up the embassy of Bajtocja! - somebody cried. Everybodyworks pretty goodegabyand andradiocars appeared near the embassy only fewseconds after the explo. All the people

11、 near the embassy were detained. Some of these people aretheanizers of the explo, but the others could by just occaal witnesses. During thetestification eachnamed exactly one petrator. It is known,t if a man is notrpetrator,n he always says the truth (he havent a reason to, have he?). However, petra

12、tors want tomake the work of themore difficult, sorpetrator can name anyduring thetestification (even himself).第 6頁(yè) 共 8 頁(yè)for i:=1 to n do begin prei:=lastfind(i);lastfind(i):=i;end;for ians:=0;for i:=1 to m do begin build(ci.x);k1:=dp(lchci.x,1)+1; build(ci.y);k2:=dp(lchci.y,1)+1;if k1k2 then ans:=a

13、ns+k1 else ans:=ans+k2; end;for iwrin(ans); end;for testEND.IOI2009by Jia Zhihao from No.2 Middle School in Shijiazh uangThemen arehe very hard situation. They should arrest some group of potential petrators,but it is difficult to determine who is guilty and who is not from the dahey have. There exi

14、sts manygroups of potential petrators,t dont contradict to any of the testimonies. Themen want toarrest as small innocent people assible. So they would like to choose the group with minimal number of people.Write a programt, given the number of detained people and their testimonies, will determine t

15、henumber of peoplehe smallest group of potential p testimonies.etrators,t dont contradict to theInputTheline of the inpontains a singleeger T, the number of testcases (1=T=10).line of each testcase containseger number N (2 = N = 100000), equal to the number ofdetained people (the people are numbered

16、 from 1 to N). The i-th of the following N lines contain oneeger numbi (1 = Pi = N). Heris the man whom i-th man testified to be guilty.OutputThe output should consist of T lines, containing oneeger number for each testcase - the number of t dont contradict to the testimonies.peoplehe smallest group of potential petrators,ExleInput:1