• 「BZOJ2100」[Usaco2010 Dec] Apple Delivery

    「BZOJ2100」[Usaco2010 Dec] Apple Delivery

    DescriptionBessiehastwocrispredapplestodelivertotwoofherfriendsintheherd.Ofcourse,shetravelstheC(1<=C<=200,000)cowpathswhicharearrangedastheusualgraphwhichconnectsP(1<=P<=100,000)pasturesconvenientlynumberedfrom1..P:nocowpathleadsfromapasturetoitself,cowpathsarebidirectional,eachcowpathhasanassociateddistance,and,bestofall,itisalwayspossibletogetfromanypasturetoanyotherpasture....

    02014年7月29日3,836spfa
  • 「BZOJ2015」[Usaco2010 Feb] Chocolate Giving

    「BZOJ2015」[Usaco2010 Feb] Chocolate Giving

    DescriptionFarmerJohn有B头奶牛(1<=B<=25000),有N(2*B<=N<=50000)个农场,编号1-N,有M(N-1<=M<=100000)条双向边,第i条边连接农场R_i和S_i(1<=R_i<=N;1<=S_i<=N),该边的长度是L_i(1<=L_i<=2000)。居住在农场P_i的奶牛A(1<=P_i<=N),它想送一份新年礼物给居住在农场Q_i(1<=Q_i<=N)的奶牛B,但是奶牛A必须先到FJ(居住在编号1的农场)那里取礼物,...

    02014年7月29日3,865spfa
  • 「NOIP模拟赛」笨笨的电话网络

    「NOIP模拟赛」笨笨的电话网络

    多年以后,笨笨长大了,成为了电话线布置师。由于地震使得某市的电话线全部损坏,笨笨是负责接到震中市的负责人。该市周围分布着N(1≤N≤1000)根据1…n顺序编号的废弃的电话线杆,任意两根线杆之间没有电话线连接,一共有p(0≤p≤10000)对电话杆可以拉电话线。其他的由于地震使得无法连接。第i对电线杆的两个端点分别是ai,bi,它们的距离为li(1≤li≤1000000)。数据中每对(ai,bi)只出现一次。编号为1的电话杆已经接入了全国的电...

    02014年7月8日3,837spfa,二分法
  • 「NOIP模拟赛」坑爹的GPS

    「NOIP模拟赛」坑爹的GPS

    坑爹的GPS(gpsduel.c/.cpp/.pas)有一天,FJ买了一辆车,但是,他一手下载了两个GPS系统。好了现在麻烦的事情来了,GPS有一个功能大概大家也知道,如果FJ没有按照GPS内置地图的最短路走,GPS就会报错来骚扰你。现在FJ准备从他的农舍(在1这个点)开车到他的谷屋(n这个点)。FJ给了你两个GPS系统内置地图的信息,他想知道,他最少会听到多少次报错(如果FJ走的路同时不满足两个GPS,报错次数+2)读...

    22014年7月3日3,592最短路
  • 「BZOJ1179」[Apio2009] 抢掠计划atm

    「BZOJ1179」[Apio2009] 抢掠计划atm

    DescriptionInput第一行包含两个整数N、M。N表示路口的个数,M表示道路条数。接下来M行,每行两个整数,这两个整数都在1到N之间,第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行,每行一个整数,按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P,S表示市中心的编号,也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数,表示P个有酒吧的路口的编号Output输出一个...

    02014年6月16日5,958spfa,图的连通
  • 「BZOJ1715」[Usaco2006 Dec] Wormholes 虫洞

    「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日6,717spfa
  • 「BZOJ1631」[Usaco2007 Feb] Cow Party

    「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,388spfa
  • 「1612」[Usaco2008 Jan] Cow Contest奶牛的比赛

    「1612」[Usaco2008 Jan] Cow Contest奶牛的比赛

    DescriptionFJ的N(1<=N<=100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上,奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同,并且没有哪两头奶牛的水平不相上下,也就是说,奶牛们的编程能力有明确的排名。整个比赛被分成了若干轮,每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1<=A<=N;1<=B<=N;A!=B),那么她们的对决中,编号为A的奶牛总是能胜出。F...

    02014年5月22日5,368floyd
  • 「BZOJ1690」[Usaco2007 Dec] 奶牛的旅行

    「BZOJ1690」[Usaco2007 Dec] 奶牛的旅行

    Description作为对奶牛们辛勤工作的回报,FarmerJohn决定带她们去附近的大城市玩一天。旅行的前夜,奶牛们在兴奋地讨论如何最好地享受这难得的闲暇。很幸运地,奶牛们找到了一张详细的城市地图,上面标注了城市中所有L(2<=L<=1000)座标志性建筑物(建筑物按1..L顺次编号),以及连接这些建筑物的P(2<=P<=5000)条道路。按照计划,那天早上FarmerJohn会开车将奶牛们送到某个她们指定的建筑物旁边,等奶牛们完成...

    32014年5月19日4,887spfa
  • 「NOIP模拟赛」虫洞

    「NOIP模拟赛」虫洞

    「题目描述」N个虫洞,M条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和1单位时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为delta。从白洞跃迁到黑洞,消耗的燃料值减少delta,若该条路径消耗的燃料值变为负数的话,取为0。从黑洞跃迁到白洞,消耗的燃料值增加delta。路径两端均为黑洞或白洞,消耗的燃料值不变化。作为压轴题,自然不会是如此简单的最短路问题,所以每过1单位时间黑洞...

    02014年5月10日4,537spfa
  • 「BZOJ1641」[Usaco2007 Nov] Cow Hurdles 奶牛跨栏

    「BZOJ1641」[Usaco2007 Nov] Cow Hurdles 奶牛跨栏

    DescriptionFarmerJohn想让她的奶牛准备郡级跳跃比赛,贝茜和她的伙伴们正在练习跨栏。她们很累,所以她们想消耗最少的能量来跨栏。显然,对于一头奶牛跳过几个矮栏是很容易的,但是高栏却很难。于是,奶牛们总是关心路径上最高的栏的高度。奶牛的训练场中有N(1≤N≤300)个站台,分别标记为1..N。所有站台之间有M(1≤M≤25,000)条单向路径,第i条路经是从站台Si开始,到站台Ei,其中最高的栏的高度为Hi(1≤Hi≤1,000,0...

    12014年4月16日3,542floyd
  • 「POJ1556」The Doors

    「POJ1556」The Doors

    DescriptionYouaretofindthelengthoftheshortestpaththroughachambercontainingobstructingwalls.Thechamberwillalwayshavesidesatx=0,x=10,y=0,andy=10.Theinitialandfinalpointsofthepatharealways(0,5)and(10,5).Therewillalsobefrom0to18verticalwallsinsidethechamber,eachwithtwodoorways.Thefigurebelowillustratessuchachamberandalsoshowsthepathofminimallength.InputTheinputdatafortheillustratedchamberwould...

    02014年4月12日4,957spfa,几何