« 上一页下一页 »Current position : 首页 >> 图论 >> 第10页
「POJ2404」Jogging Trails
DescriptionGordistrainingforamarathon.Behindhishouseisaparkwithalargenetworkofjoggingtrailsconnectingwaterstations.Gordwantstofindtheshortestjoggingroutethattravelsalongeverytrailatleastonce.InputInputconsistsofseveraltestcases.Thefirstlineofinputforeachcasecontainstwopositiveintegers:n<=15,thenumberofwaterstations,andm<1000,thenumberoftrails.Foreachtrail,thereisonesubsequentlineofin...
「SPOJ1825」Free tour II
Afterthesuccessof2ndanniversary(takealookatproblemFTOURformoredetails),this3rdyear,TravelAgentSPOJgoesonwithanotherdiscounttour.ThetourwillbeheldonICPCisland,amiraculousoneonthePacificOcean.WelistNplaces(indexedfrom1toN)wherethevisitorscanhaveatrip.Eachroadconnectingthemhasaninterestvalue,andthisvaluecanbenegative(ifthereisnothinginterestingtoviewthere).Simply,theseNplaces...
「CF500E」New Year Domino
Celebratingthenewyear,manypeoplepostvideosoffallingdominoes;Here'salistofthem:https://www.youtube.com/results?search_query=New+Years+DominosUserainta,wholivesina2Dworld,isgoingtopostavideoaswell.Therearendominoesona2DCartesianplane.i-thdomino(1 ≤ i ≤ n)canberepresentedasalinesegmentwhichisparalleltothey-axisandwhoselengthisli.Thelowerpointofthedominoisonthex-axis.Let'sdenotethex-...
「CF500B」New Year Permutation
Useraintahasapermutationp1, p2, ..., pn.AstheNewYeariscoming,hewantstomakehispermutationasprettyaspossible.Permutationa1, a2, ..., anisprettierthanpermutationb1, b2, ..., bn,ifandonlyifthereexistsanintegerk(1 ≤ k ≤ n)wherea1 = b1, a2 = b2, ..., ak - 1 = bk - 1andak < bkallholds.Asknown,permutationpissosensitivethatitcouldbeonlymodifiedbyswappingtwodistinctele...
「POJ1637」Sightseeing tour
DescriptionThecityexecutiveboardinLundwantstoconstructasightseeingtourbybusinLund,sothattouristscanseeeverycornerofthebeautifulcity.Theywanttoconstructthetoursothateverystreetinthecityisvisitedexactlyonce.Thebusshouldalsostartandendatthesamejunction.Asinanycity,thestreetsareeitherone-wayortwo-way,trafficrulesthatmustbeobeyedbythetourbus.Helptheexecutiveboardanddetermineifit'spossibletocons...
「zoj2760」How Many Shortest Path
Givenaweighteddirectedgraph,wedefinetheshortestpathasthepathwhohasthesmallestlengthamongallthepathconnectingthesourcevertextothetargetvertex.Andiftwopathissaidtobenon-overlapping,itmeansthatthetwopathhasnocommonedge.So,givenaweighteddirectedgraph,asourcevertexandatargetvertex,weareinterestedinhowmanynon-overlappingshortestpathcouldwefindoutatmost.InputInputconsistsofmultipletestcases.Thefirs...
「BZOJ2400」SPOJ 839 Optimal Marks
Description定义无向图中的一条边的值为：这条边连接的两个点的值的异或值。定义一个无向图的值为：这个无向图所有边的值的和。给你一个有n个结点m条边的无向图。其中的一些点的值是给定的，而其余的点的值由你决定（但要求均为非负数），使得这个无向图的值最小。在无向图的值最小的前提下，使得无向图中所有点的值的和最小。Input第一行，两个数n，m，表示图的点数和边数。接下来n行，每行一个数，按编号给出每个点的值（若为负...
「网络流24题」最长递增子序列问题
题意有些奇怪任务（2）是取出。。。且题中递增是非严格递增我的代码任务3若能取出无限多的序列，则输出-1输入41324输出3 1 2样例2输入43625输出2 2 -1搬运byvoid神犇题解「问题分析」第一问是LIS，动态规划求解，第二问和第三问用网络最大流解决。「建模方法」首先动态规划求出F[i]，表示以第i位为开头的最长上升序列的长度，求出最长上升序列长度K。1、把序列每位i拆成两个点<i.a>和<i.b>，从<i.a>到&...
「网络流24题」最长k可重区间集问题
搬运byvoid的题解「问题分析」最大权不相交路径问题，可以用最大费用最大流解决。「建模方法」方法1按左端点排序所有区间，把每个区间拆分看做两个顶点<i.a><i.b>，建立附加源S汇T，以及附加顶点S'。1、连接S到S'一条容量为K，费用为0的有向边。2、从S'到每个<i.a>连接一条容量为1，费用为0的有向边。3、从每个<i.b>到T连接一条容量为1，费用为0的有向边。4、从每个顶点<i.a>到<i.b>连...
「POJ1149」PIGS
DescriptionMirkoworksonapigfarmthatconsistsofMlockedpig-housesandMirkocan'tunlockanypighousebecausehedoesn'thavethekeys.Customerscometothefarmoneafteranother.Eachofthemhaskeystosomepig-housesandwantstobuyacertainnumberofpigs.AlldataconcerningcustomersplanningtovisitthefarmonthatparticulardayareavailabletoMirkoearlyinthemorningsothathecanmakeasales-planinordertomaximizethenumberofpigssold.M...
「泉七培训 – 杨国烨」图
「题目描述」给一张联通无向图，定义Dist[i][j]表示点i到点j之间的最短路。当前已经有了若干条的边，再给定N个A[i]，要求添加若干条无向边，使得Σ(a[i]-Dist[1][i])^2最小。输出最小的答案。「输入格式」第一行是整数N，表示节点数。接下来是N*N的矩阵，mat[i][j]=‘Y’表示i和j之间有一条无向边。保证mat[i][j]=mat[j][i]。接下来N个数，表示A[i]。「输出格式」求答案。「样例输入」4NYNNYNYNNYNYNNYN...
「泉七培训 – 刘定峰」链型网络
题意给定一张无重边，自环的无向图每次可以加边，或者询问有多少个点满足将该点删除后，原图的每个连通块都为一条链 数据范围30%的数据n<=100m<=2n100%的数据n<=100000,m<=2n 题解30分很简单对于每次询问枚举删去每一个点，然后再用O（n）的时间在图上判环以及度数是否都小等于2 然后正解。。。考虑以下一些简单的情况原图为若干条链，则答案为点数N原图为单个简单环加若干条链，则答案为环大小原图中...
OI 课件=>
近期评论