• 「BZOJ2407」探险

    「BZOJ2407」探险

    Description探险家小T好高兴!X国要举办一次溶洞探险比赛,获奖者将得到丰厚奖品哦!小T虽然对奖品不感兴趣,但是这个大振名声的机会当然不能错过!比赛即将开始,工作人员说明了这次比赛的规则:每个溶洞和其他某些溶洞有暗道相连。两个溶洞之间可能有多条道路,也有可能没有,但没有一条暗道直接从自己连到自己。参赛者需要统一从一个大溶洞出发,并再次回到这个大溶洞。如果就这么点限制,那么问题就太简单了,可是举办方又...

    12014年11月27日2,254STL,dijkstra
  • 「BZOJ2259」[Oibh] 新型计算机

    「BZOJ2259」[Oibh] 新型计算机

    DescriptionTim正在摆弄着他设计的“计算机”,他认为这台计算机原理很独特,因此利用它可以解决许多难题。但是,有一个难题他却解决不了,是这台计算机的输入问题。新型计算机的输入也很独特,假设输入序列中有一些数字(都是自然数——自然数包括0),计算机先读取第一个数字S1,然后顺序向后读入S1个数字。接着再读一个数字S2,顺序向后读入S2个数字……依此类推。不过只有计算机正好将输入序列中的数字读完,它才能正确处...

    02014年11月25日1,955STL,dijkstra
  • 「NOIP模拟赛」长途旅行

    「NOIP模拟赛」长途旅行

    「题目描述」JY是一个爱旅游的探险家,也是一名强迫症患者。现在JY想要在C国进行一次长途旅行,C国拥有n个城市(编号为0,1,2...,n-1),城市之间有m条道路,可能某个城市到自己有一条道路,也有可能两个城市之间有多条道路,通过每条道路都要花费一些时间。JY从0号城市开始出发,目的地为n–1号城市。由于JY想要好好参观一下C国,所以JY想要旅行恰好T小时。为了让自己的旅行更有意思,JY决定不在任何一个时刻停留(走...

    32014年11月3日2,758spfa
  • 「BZOJ1665」[Usaco2006 Open] The Climbing Wall 攀岩

    「BZOJ1665」[Usaco2006 Open] The Climbing Wall 攀岩

    DescriptionOneofthemostpopularattractionsatthecountyfairistheclimbingwall.Bessiewantstoplanhertripupthewallinadvanceandneedsyourhelp.Thewallis30,000millimeterswideandH(1001<=H<=30,000)millimetershighandhasF(1<=F<=10,000)hoof-holdsatuniqueX,Ycoordinatesexpressedinmillimeters.0,0isatthegroundlevelontheleftsideofthewall.Hoof-holdsareseparatedbyatleast300millimeterssincenocowcan...

    02014年10月29日1,971STL,dijkstra
  • 「NOIP模拟赛」花园的守护之神

    「NOIP模拟赛」花园的守护之神

    题目描述看着正在被上古神兽们摧残的花园,花园的守护之神――小Bug同学泪流满面。然而,FZOI不相信眼泪,小bug与神兽们的战争将进行到底!通过google,小Bug得知,神兽们来自遥远的戈壁。为了扭转战局,小Bug决定拖延神兽增援的速度。从戈壁到达花园的路径错综复杂,由若干段双向的小路组成。神兽们通过每段小路都需要一段时间。小Bug可以通过向其中的一些小路投掷小xie来拖延神兽。她可以向任意小路投掷小Xie,而且可以...

    32014年10月28日2,143STL,最小割,dijkstra
  • 「NOIP模拟赛」小奇回地球

    「NOIP模拟赛」小奇回地球

    原题目名:时间与空间之旅2015.9.13日hzwer重制了题面与数据「题目背景」开学了,小奇在回地球的路上,遇到了一个棘手的问题。 「问题描述」简单来说,它要从标号为1的星球到标号为n的星球,某一些星球之间有航线。由于超时空隧道的存在,从一个星球到另一个星球时间可能会倒流,而且,从星球a到b耗费的时间和星球b到a耗费的时间不一定相同。 宇宙法规定:“禁止在出发时间前到达目的地。”每艘飞船上都有速度调节装置,...

    32014年10月28日2,371spfa,二分法
  • 「BZOJ2709」[Violet 1] 迷宫花园

    「BZOJ2709」[Violet 1] 迷宫花园

    DescriptionInputOutputSampleInput22.545######S##E######211312#############S###E#####################################################################SampleOutput0.500000.21053HINTSource题解。。。。二分+最短路判定即可不知道为何读入会出现奇怪的问题让我re了一版。。。。一直检查数组。。。[crayon-5b281884b6060556674148/] ...

    02014年10月27日2,189STL,dijkstra,二分法
  • 「BZOJ2143」飞飞侠

    「BZOJ2143」飞飞侠

    Description飞飞国是一个传说中的国度,国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵,每个格子代表一个街区。然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么,任何飞飞侠都只需要在(i,j)支付Aij的费用...

    02014年10月23日3,148STL,dijkstra
  • 「BZOJ1097」[POI2007] 旅游景点atr

    「BZOJ1097」[POI2007] 旅游景点atr

    DescriptionFGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景,品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的,比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山,而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的,他可以在某些旅行方案之间进行选择。由于FGD非常讨厌乘车的颠簸,他希望在满足他的要求的情况下,旅行的距离尽量短,这样他就有足...

    02014年10月19日3,360dijkstra,状压动规
  • 「codecomb2090」最小乘积路

    「codecomb2090」最小乘积路

    题目描述给定n个点的带权有向图,求从1到n的路径中边权之积最小的简单路径。输入格式第一行读入两个整数n,m,表示共n个点m条边。接下来m行,每行三个正整数x,y,z,表示点x到点y有一条边权为z的边。输出格式输出仅包括一行,记为所求路径的边权之积,由于答案可能很大,因此输出它模9987的余数即可。样例数据1输入331232331310输出9备注对于20%的数据,n<=10。对于100%的数据,n<=1000,m<=1000000。边权不超过10000。题...

    02014年10月13日1,594dijkstra
  • 「BZOJ2324」[ZJOI2011] 营救皮卡丘

    「BZOJ2324」[ZJOI2011] 营救皮卡丘

    Description皮卡丘被火箭队用邪恶的计谋抢走了!这三个坏家伙还给小智留下了赤果果的挑衅!为了皮卡丘,也为了正义,小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。火箭队一共有N个据点,据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发,营救被困在N号据点的皮卡丘。为了方便起见,我们将真新镇视为0号据点,一开始K个人都在0号点。由于火箭队的重重布防,要想摧毁K号据点,必须按照顺序先摧...

    02014年10月9日4,154费用流,floyd
  • 「BZOJ3389」[Usaco2004 Dec] Cleaning Shifts安排值班

    「BZOJ3389」[Usaco2004 Dec] Cleaning Shifts安排值班

    Description    一天有T(1≤T≤10^6)个时段.约翰正打算安排他的N(1≤N≤25000)只奶牛来值班,打扫打扫牛棚卫生.每只奶牛都有自己的空闲时间段[Si,Ei](1≤Si≤Ei≤T),只能把空闲的奶牛安排出来值班.而且,每个时间段必需有奶牛在值班.  那么,最少需要动用多少奶牛参与值班呢?如果没有办法安排出合理的方案,就输出-1.Input    第1行:N,T.    第2到N+1行:Si,Ei.Output    最少安排...

    32014年10月1日1,813dijkstra