第二次作业解题报告-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题目大意设图 G 有 N 个点，每个点恰好向外连一条有向边，现在让你找出最小的点集S，使得对于任何不属于 S 的点，有向边一定连向属于 S 的点。解题方法首先， 以单独考虑每可以发现，有向图的连通分支之间是相互没有影响的，所以通分支。可对于每通分支，它的结构都大致如下图。可以只要将图中的环上删去一个点，

2、那么原图就变成了一棵树，且每个点的有向边恰好连向他的父节点。于是不难想到：可以将图转化成树形 DP 来做。第 1 页 共 8 页IOI2009by Jia Zhihao from No.2 Middle School in Shijiazh uang方法如下：对于每通分支，任意找环上的一条边，则他两端的点至少有一个在S 中，枚哪个点在 S 中，之后可以去掉枚举的点向外连的有向边，该连通分支转化成了树。下面两幅图为两种情况。对于每一种情况，用树形 DP 计算|S|的最小值。子-右兄弟的二叉表示法表示，用lch(v) 表示v 的先将多叉树用子， rch(v) 表示 v 的右儿子。定义dp(v,0)

3、 表示v 的父亲节点属于 S 时， v 在二叉表示的子树中，最少有几个节点属于 S；定义dp(v,1) 表示 v 的父亲节点不属于 S 时， v 在二叉表示的子树中，最少有几个节点属于 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、是最终。总结第 2 页 共 8 页IOI2009by Jia Zhihao from No.2 Middle School in Shijiazh uang要发现题目的特点：图 G 有 N 个点，每个点恰好向外连一条有向边，则图 G 的每通分支有且仅有一个环。多叉树的子-右兄弟的二叉表示法。用 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