图论 - Page 20 - hzwer.com

「BZOJ3504」[CQOI2014] 危桥
DescriptionAlice和Bob居住在一个由N座岛屿组成的国家，岛屿被编号为0到N-1。某些岛屿之间有桥相连，桥上的道路是双向的，但一次只能供一人通行。其中一些桥由于年久失修成为危桥，最多只能通行两次。Alice希望在岛屿al和a2之间往返an次（从al到a2再从a2到al算一次往返）。同时，Bob希望在岛屿bl和b2之间往返bn次。这个过程中，所有危桥最多通行两次，其余的桥可以无限次通行。请问Alice和Bob能完成他们的愿望吗？Input本...
22014年6月21日5,409最大流

「泉七培训 – 郑予凡」雷神领域
此题数据水，各种骗分。。。二维偏序最长链，两个方向最小值40分。。。直接统计不同的x，y坐标个数输出最小值70分。。。正解似乎比较奇怪。。。懒得解释了[crayon-6743db66b4809735433226/] ...
12014年6月21日2,742并查集
「BZOJ2502」清理雪道
Description 滑雪场坐落在FJ省西北部的若干座山上。从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。由于每次飞行的耗费是固定的，为了最小化耗费，你想知...
02014年6月17日5,600有上下界网络流
「BZOJ2055」80人环游世界
DescriptionInput第一行两个正整数N，M。第二行有N个不大于M正整数，分别表示V1，V2......VN。接下来有N¡1行。第i行有N¡i个整数，该行的第j个数表示从第i个国家到第i+j个国家的机票费（如果该值等于¡1则表示这两个国家间没有通航）。Output在第一行输出最少的总费用。SampleInput632131212685082416104-14SampleOutput27HINT1<=N<=1001<=M<=79题解m个人的起始点任意。。。这什么奇怪的设定。...
02014年6月17日4,684有上下界网络流
「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日6,289spfa,图的连通
「BZOJ1532」[POI2005] Kos – Dicing
DescriptionDicing是一个两人玩的游戏,这个游戏在Byteotia非常流行.甚至人们专门成立了这个游戏的一个俱乐部.俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人.现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.Input第一行两个整数n和m,1<=n<=10000,0<=m<=...
02014年6月15日4,321最小割,二分法
「POJ1741」Tree
DescriptionGiveatreewithnvertices,eachedgehasalength(positiveintegerlessthan1001).Definedist(u,v)=Themindistancebetweennodeuandv.Giveanintegerk,foreverypair(u,v)ofverticesiscalledvalidifandonlyifdist(u,v)notexceedk.Writeaprogramthatwillcounthowmanypairswhicharevalidforagiventree.InputTheinputcontainsseveraltestcases.Thefirstlineofeachtestcasecontainstwointegersn,k.(n<=10000)Thefollowi...
122014年6月15日9,825点分治
「BZOJ1930」[SHOI2003] pacman吃豆豆
Description两个PACMAN吃豆豆。一开始的时候，PACMAN都在坐标原点的左下方，豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。请你帮这两个PACMAN计算一下，他们俩加起来最多能吃掉多少豆豆。Input第一行为一个整数N，表示豆豆的数目。接下来N行，每行一对正整数，表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。O...
112014年6月14日6,106费用流
「泉七培训 – 黄施霖」最近公共祖先
第一次做交互题。。。可以任意询问俩点的lca，然后要求回答出树的形态，最多50000个点各种乱搞搞了90分首先对于一条链的情况可以用平衡树维护点之间的关系，不过如果直接写个快排也是可以的那么对于一棵树可以这样考虑假设我们大致知道了前i个点的情况，这时候加入一个点x先求其与当前根root的lca设为t，如果t=x，那么fa[root]=x,ls[x]=root,root=x否则有两种情况，x在root的左子树，或者在右子树，就可以递归下去所以只要先选俩个...
12014年6月14日4,198最近公共祖先
「codechefCHSEQ22」Chef and Favourite Sequence
Allsubmissionsforthisproblemareavailable.Readproblemsstatementsin MandarinChinese and Russian.Chefhasanintegersequence a1, a2,..., aN ofsize N,wherealltheelementsofthesequenceare 0initially.Chefalsohas M segments,herethe ith oneis [Li,Ri].Hewantstocreatenewsequencesusingthefollowingoperation:Inasingleoperation,hepicksasegmentfromthe M segments.Letthechosensegmentbe ...
02014年6月13日826并查集
「BZOJ1146」[CTSC2008] 网络管理Network
DescriptionM公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的N个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。该网络的结构由N个路由器和N-1条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通...
22014年6月13日7,684treap,树套树,二分法,线段树,树链剖分
「BZOJ3531」[SDOI2014] 旅行
Description S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，...
32014年6月13日7,260线段树,树链剖分