• 【bzoj3931】[CQOI2015]网络吞吐量

    【bzoj3931】[CQOI2015]网络吞吐量

    题意即题解最短路+网络流1A了赞233[crayon-58d366b558c3f676932006/] 

    82015年4月7日1,665STL,dijkstra,最大流
  • [jsoi2010]旅行

    [jsoi2010]旅行

    给定一张无向图,可以k次交换两条边边权,求1到n的最短路交换执行于求最短路之前,边权1<=c<=1000点数<=50边数<=150k<=20此题找不到题解求神犇留言做法我的想法。。。先求从1-n,无视i条边边权的最短路,然后在路径外找i条最短的加回去。。最后只对了5个点。。。[crayon-58d366b5594d2882621051/] ...

    12015年3月23日1,098STL,spfa
  • 【poj2404】Jogging Trails

    【poj2404】Jogging Trails

    DescriptionGordistrainingforamarathon.Behindhishouseisaparkwithalargenetworkofjoggingtrailsconnectingwaterstations.Gordwantstofindtheshortestjoggingroutethattravelsalongeverytrailatleastonce.InputInputconsistsofseveraltestcases.Thefirstlineofinputforeachcasecontainstwopositiveintegers:n<=15,thenumberofwaterstations,andm<1000,thenumberoftrails.Foreachtrail,thereisonesubsequentlineofin...

    02015年1月2日1,075floyd,状压动规
  • 【zoj2760】How Many Shortest Path

    【zoj2760】How Many Shortest Path

    Givenaweighteddirectedgraph,wedefinetheshortestpathasthepathwhohasthesmallestlengthamongallthepathconnectingthesourcevertextothetargetvertex.Andiftwopathissaidtobenon-overlapping,itmeansthatthetwopathhasnocommonedge.So,givenaweighteddirectedgraph,asourcevertexandatargetvertex,weareinterestedinhowmanynon-overlappingshortestpathcouldwefindoutatmost.InputInputconsistsofmultipletestcases.Thefirs...

    02014年12月27日920floyd,最大流
  • 【bzoj1486】[HNOI2009]最小圈

    【bzoj1486】[HNOI2009]最小圈

    题解分数规划,二分答案用dfs版的spfa判负环[crayon-58d366b55a157716269723/] 

    02014年12月23日1,977spfa,二分法
  • 【bzoj1922】[Sdoi2010]大陆争霸

    【bzoj1922】[Sdoi2010]大陆争霸

    Description在一个遥远的世界里有两个国家:位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神:杰森国信仰象征黑暗和毁灭的神曾·布拉泽,而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。幻想历8012年1月,杰森国正式宣布曾·布拉泽是他们唯一信仰的神,同时开始迫害在杰森国的信仰斯普林·布拉泽的克里斯国教徒。幻想历8012年3月2日,位于杰森国东部小镇神谕镇的克里斯国教徒发动起义。幻想...

    22014年12月22日1,763STL,dijkstra
  • 【bzoj2718/1143】[Violet 4]毕业旅行

    【bzoj2718/1143】[Violet 4]毕业旅行

    DescriptionInputOutput最多可选多少景点SampleInput76122354433667SampleOutput2HINT题解最长反链=最小路径覆盖。。。至于证明。。。百度vfk的博客floyd传递闭包后,用n-二分图最大匹配数即为答案[crayon-58d366b55ab00255225068/] ...

    02014年12月22日1,419floyd,最大流
  • NOI2010海拔

    NOI2010海拔

    DescriptionYT市是一个规划良好的城市,城市被东西向和南北向的主干道划分为n×n个区域。简单起见,可以将YT市看作一个正方形,每一个区域也可看作一个正方形。从而,YT城市中包括(n+1)×(n+1)个交叉路口和2n×(n+1)条双向道路(简称道路),每条双向道路连接主干道上两个相邻的交叉路口。下图为一张YT市的地图(n=2),城市被划分为2×2个区域,包括3×3个交叉路口和12条双向道路。小Z作为该市的市长,他根据统计信息得到...

    02014年12月17日1,188最小割,STL,dijkstra
  • 【bzoj4016】[FJOI2014]最短路径树问题

    【bzoj4016】[FJOI2014]最短路径树问题

    cxjyxx_me:先求一个最短路图然后再这个图上dfs对于一个点的所有出点按编号从小到大dfs这样可以保证dfs树就是题目要求的树然后在这棵树上跑树分治f[i][j][2]表示前i棵子树从根出发链长为j[0:最长长度][1:这个长度条件下的方案数]对于第i+1棵子树单独跑一个f’[i][j][2]意义一样枚举这颗子树上链长和f一起更新答案然后用f‘更新f[crayon-58d366b56980d119579775/] ...

    52014年12月15日2,645STL,dijkstra,点分治
  • 【bzoj1027】[JSOI2007]合金

    【bzoj1027】[JSOI2007]合金

    Description某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料,不同种类的原材料中铁铝锡的比重不同。然后,将每种原材料取出一定量,经过融解、混合,得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。现在,用户给出了n种他们需要的合金,以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料,并且使用这些原材料可以加工出用户需要的所有种类的合金。Input第一行两个...

    72014年12月9日2,295floyd,几何
  • 【bzoj2407】探险

    【bzoj2407】探险

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

    12014年11月27日1,115STL,dijkstra
  • 【bzoj2259】[Oibh]新型计算机

    【bzoj2259】[Oibh]新型计算机

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

    02014年11月25日1,273STL,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日1,641spfa