第二次作業(yè)解題報告-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 個點，每個點恰好向外連一條有向邊，現(xiàn)在讓你找出最小的點集S，使得對于任何不屬于 S 的點，有向邊一定連向?qū)儆?S 的點。解題方法首先， 以單獨考慮每可以發(fā)現(xiàn)，有向圖的連通分支之間是相互沒有影響的，所以通分支。可對于每通分支，它的結(jié)構(gòu)都大致如下圖?？梢灾灰獙D中的環(huán)上刪去一個點，

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

3、 表示v 的父親節(jié)點屬于 S 時， v 在二叉表示的子樹中，最少有幾個節(jié)點屬于 S；定義dp(v,1) 表示 v 的父親節(jié)點不屬于 S 時， v 在二叉表示的子樹中，最少有幾個節(jié)點屬于 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特別的，于是，可以通過這個方法求出每通分支的 min|S|，相加起來就

4、是最終。總結(jié)第 2 頁 共 8 頁IOI2009by Jia Zhihao from No.2 Middle School in Shijiazh uang要發(fā)現(xiàn)題目的特點：圖 G 有 N 個點，每個點恰好向外連一條有向邊，則圖 G 的每通分支有且僅有一個環(huán)。多叉樹的子-右兄弟的二叉表示法。用 DP解決樹。附代碼第 3 頁 共 8 頁IOI2009by Jia Zhihao from No.2 Middle School in Shijiazh uang第 4 頁 共 8 頁PROGRAM 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 頁 共 8 頁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頁 共 8 頁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