树形动规 - Page 5

「BZOJ1596」[Usaco2008 Jan] 电话网络
DescriptionFarmerJohn决定为他的所有奶牛都配备手机，以此鼓励她们互相交流。不过，为此FJ必须在奶牛们居住的N(1<=N<=10,000)块草地中选一些建上无线电通讯塔，来保证任意两块草地间都存在手机信号。所有的N块草地按1..N顺次编号。所有草地中只有N-1对是相邻的，不过对任意两块草地A和B(1<=A<=N;1<=B<=N;A!=B)，都可以找到一个以A开头以B结尾的草地序列，并且序列中相邻的编号所代表的草地...
02014年7月7日4,414贪心,树形动规

「BZOJ1827」[Usaco2010 Mar] gather 奶牛大集会
DescriptionBessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1<=A_i<=N;1<=B_i<=N),长度为L_i(1<=L_i<=1,000)。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居...
02014年5月19日4,186贪心,树形动规
「POJ3107」Godfather
DescriptionLastyearsChicagowasfullofgangsterfightsandstrangemurders.Thechiefofthepolicegotreallytiredofallthesecrimes,anddecidedtoarrestthemafialeaders.Unfortunately,thestructureofChicagomafiaisrathercomplicated.Thereare n personsknowntoberelatedtomafia.Thepolicehavetracedtheiractivityforsometime,andknowthatsomeofthemarecommunicatingwitheachother.Basedonthedatacollected,thechiefofthepol...
12014年4月1日4,779树形动规
「POJ1655」Balancing Act
DescriptionConsideratreeTwithN(1<=N<=20,000)nodesnumbered1...N.Deletinganynodefromthetreeyieldsaforest:acollectionofoneormoretrees.DefinethebalanceofanodetobethesizeofthelargesttreeintheforestTcreatedbydeletingthatnodefromT.Forexample,considerthetree:Deletingnode4yieldstwotreeswhosemembernodesare{5}and{1,2,3,6,7}.Thelargerofthesetwotreeshasfivenodes,thusthebalanceofnode4isfive.D...
12014年4月1日4,292树形动规
「th04」秋静叶&秋穣子
Description在幻想乡，秋姐妹是掌管秋天的神明，作为红叶之神的姐姐静叶和作为丰收之神的妹妹穰子。如果把红叶和果实联系在一起，自然会想到烤红薯。烤红薯需要很多的叶子，才能把红薯烤得很香，所以秋姐妹决定比比谁能够收集到最多的红叶。静叶将红叶分成了N堆(编号1..N)，并且规定了它们的选取顺序，刚好形成一颗有向树。在游戏过程中，两人从根节点开始，轮流取走红叶，当一个人取走节点i的红叶后，另一个人只能从节点i的儿子...
02014年3月23日3,712树形动规,博弈论
「BZOJ1040」[ZJOI2008] 骑士
DescriptionZ国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。最近发生了一件可怕的事情，邪恶的Y国发动了一场针对Z国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的Z国又怎能抵挡的住Y国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相...
02014年2月26日8,864递推与动规,深度搜索,树形动规
「vijos1642」班长的任务
背景十八居士的毕业典礼（1）描述福州时代中学2009届十班同学毕业了，于是班长PRT开始筹办毕业晚会，但是由于条件有限，可能每个同学不能都去，但每个人都有一个权值，PRT希望来的同学们的权值总和最大。十班有一个周密的电话通知网络，它其实就是一棵树，根结点为班长PRT，由她来负责通知她的下线（也就是儿子节点），下线们继续通知自己的下线（不一定每个下线都要通知），任何人都可以不去：”为了使权值总和最大，班长...
02014年1月2日3,769树形动规
「CODEVS1380」没有上司的舞会
此题同「bzoj2060」[Usaco2010Nov]VisitingCows拜访奶牛题目描述Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。输入第一行一个整数N。(1<=N<=6000)接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)接...
32013年12月7日5,084树形动规