图论 - Page 21 - hzwer.com

「BZOJ2661」[BJ WC2012] 连连看
Description 凡是考智商的题里面总会有这么一种消除游戏。不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏。我们的规则是，给出一个闭区间[a,b]中的全部整数，如果其中某两个数x,y（设x>y）的平方差x2-y2是一个完全平方数z2，并且y与z互质，那么就可以将x和y连起来并且将它们一起消除，同时得到x+y点分数。那么过关的要求就是，消除的数对尽可能多的前提下，得到足够的分数。快动手动笔算一算吧。Input 只有一行...
82014年6月5日4,720费用流

「BZOJ1589」[Usaco2008 Dec] Trick or Treat on the Farm 采集糖果
Description每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N(1≤N≤100000)个牛棚里转悠，来采集糖果．她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果．农场不大，所以约翰要想尽法子让奶牛们得到快乐．他给每一个牛棚设置了一个“后继牛棚”．牛棚i的后继牛棚是Xi．他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去，就可以搜集到很多糖果．事实上这是一种有点欺骗意味的手段，来节约他的糖...
02014年6月5日4,204图的连通,记忆化搜索
「POJ2396」Budget
DescriptionWearesupposedtomakeabudgetproposalforthismulti-sitecompetition.Thebudgetproposalisamatrixwheretherowsrepresentdifferentkindsofexpensesandthecolumnsrepresentdifferentsites.Wehadameetingaboutthis,sometimeagowherewediscussedthesumsoverdifferentkindsofexpensesandsumsoverdifferentsites.Therewasalsosometalkaboutspecialconstraints:someonementionedthatComputerCenterwouldneedatleast2000K...
12014年6月3日4,091有上下界网络流
「zoj3229」Shoot the Bullet
Gensokyo isaworldwhichexistsquietlybesideours,separatedbyamysticalborder.Itisautopiawherehumansandotherbeingssuchasfairies, youkai(phantoms),andgodslivepeacefullytogether.ShameimaruAyaisacrowtenguwiththeabilitytomanipulatewindwhohasbeenin Gensokyo forover1000years.SherunstheBunbunmaruNews-anewspaperchock-fullofrumors,andownsthe Bunkachou -herrecordofinterestingobservationsforBunbun...
22014年6月3日5,952有上下界网络流
「zoj2314」Reactor Cooling
TheterroristgroupleadedbyawellknowninternationalterroristBenBladenisbulidinganuclearreactortoproduceplutoniumforthenuclearbombtheyareplanningtocreate.Beingthewickedcomputergeniusofthisgroup,youareresponsiblefordevelopingthecoolingsystemforthereactor.Thecoolingsystemofthereactorconsistsofthenumberofpipesthatspecialcoolingliquidflowsby.Pipesareconnectedatspecialpoints,callednodes,eachpipehasth...
02014年6月3日5,335有上下界网络流
「CF437D」The Child and Zoo
Ofcourseourchildlikeswalkinginazoo.Thezoohas n areas,thatarenumberedfrom 1 to n.The i-thareacontains ai animalsinit.Alsothereare m roadsinthezoo,andeachroadconnectstwodistinctareas.Naturallythezooisconnected,soyoucanreachanyareaofthezoofromanyotherareausingtheroads.Ourchildisverysmart.Imaginethechildwanttogofromarea p toarea q.Firstlyheconsidersallthesimpleroutesfrom p to q...
42014年6月1日4,033并查集
「NOIP模拟赛」密码锁
题目描述hzwer有一把密码锁，由N个开关组成。一开始的时候，所有开关都是关上的。当且仅当开关x1,x2,x3,...xk为开，其他开关为关时，密码锁才会打开。他可以进行M种的操作，每种操作有一个size[i]，表示，假如他选择了第i种的操作的话，他可以任意选择连续的size[i]个格子，把它们全部取反。（注意，由于黄金大神非常的神，所以操作次数可以无限>_<）本来这是一个无关紧要的问题，但是，黄金大神不小心他的钱丢进去了，没有...
42014年6月1日5,272费用流,广度搜索,状压动规,记忆化搜索
NOI2008志愿者招募
Description申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N天才能完成，其中第i天至少需要Ai个人。布布通过了解得知，一共有M类志愿者可以招募。其中第i类可以从第Si天工作到第Ti天，招募费用是每人Ci元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，...
22014年5月31日4,788费用流
「BZOJ1005」[HNOI2008] 明明的烦恼
Description自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?Input第一行为N(0<N<=1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1Output一个整数,表示不同的满足要求的树的个数,无解输出0SampleInput31-1-1SampleOutput2HINT 两棵树分别为1-2-3;1-3-2 题解该题运用到了...
62014年5月30日11,091高精度,prufer编码,排列组合
「BZOJ1211」[HNOI2004] 树的计数
Description一个有n个结点的树，设它的结点分别为v1,v2,…,vn，已知第i个结点vi的度数为di，问满足这样的条件的不同的树有多少棵。给定n，d1,d2,…,dn，编程需要输出满足d(vi)=di的树的个数。Input第一行是一个正整数n，表示树有n个结点。第二行有n个数，第i个数表示di，即树的第i个结点的度数。其中1<=n<=150，输入数据保证满足条件的树不超过10^17个。Output输出满足条件的树有多少棵。SampleInput42121SampleOutpu...
02014年5月30日5,246prufer编码,排列组合
「BZOJ1715」[Usaco2006 Dec] Wormholes 虫洞
DescriptionJohn在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N（从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。John将向你提供F(1<=F<=5)个农场的地图。没有小路会...
02014年5月24日7,247spfa
「BZOJ1631」[Usaco2007 Feb] Cow Party
Description 农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共有M(1≤M≤100000)条单向路连接着牛棚，第i条踣需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？Input第1行:三个用空格隔开的整数.第2行到第M+1行,每行三个用空格隔开的整数:Ai,Bi,以及Ti.表示一条道路的起点,终...
22014年5月23日3,605spfa