hzwer.com _ Home | http://hzwer.com

« 上一页下一页 »Current position : 首页 >> 图论 >> 第17页

• 「BZOJ2152」聪聪可可

  

  Description聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下...
  22014年9月7日6,530点分治

• 「BZOJ1598」[Usaco2008 Mar] 牛跑步

  

  DescriptionBESSIE准备用从牛棚跑到池塘的方法来锻炼.但是因为她懒,她只准备沿着下坡的路跑到池塘,然后走回牛棚.BESSIE也不想跑得太远,所以她想走最短的路经.农场上一共有M(1<=M<=10,000)条路,每条路连接两个用1..N(1<=N<=1000)标号的地点.更方便的是,如果X>Y,则地点X的高度大于地点Y的高度.地点N是BESSIE的牛棚;地点1是池塘.很快,BESSIE厌倦了一直走同一条路.所以她想走不同的路...
  02014年9月3日5,862dijkstra

• NOIP2012开车旅行

  

  描述小A和小B决定利用假期外出旅行，他们将想去的城市从1到N编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市i的海拔高度为Hi，城市i和城市j之间的距离d[i,j]恰好是这两个城市海拔高度之差的绝对值，即d[i,j]=|Hi-Hj|。旅行过程中，小A和小B轮流开车，第一天小A开车，之后每天轮换一次。他们计划选择一个城市S作为起点，一直向东行驶，并且最多行驶X公里就结束旅行。小A和小B的...
  22014年8月31日7,717树上倍增

• 「BZOJ3551」[ONTAK2010] Peaks加强版

  

  Description「题目描述」同3545Input第一行三个数N，M，Q。第二行N个数，第i个数为h_i接下来M行，每行3个数abc，表示从a到b有一条困难值为c的双向路径。接下来Q行，每行三个数vxk，表示一组询问。v=vxorlastans，x=xxorlastans，k=kxorlastans。如果lastans=-1则不变。Output同3545HINT「数据范围」同3545题解本题强制在线。。。据出题人的做法。。。就是做最小生成树，但合并两结点x，y的时新建结点ext，把ext连向fa...
  22014年8月30日8,977kruskal,主席树

• 「BZOJ1752」[Usaco2005 qua] Til the Cows Come Home

  

  DescriptionBessieisoutinthefieldandwantstogetbacktothebarntogetasmuchsleepaspossiblebeforeFarmerJohnwakesherforthemorningmilking.Bessieneedsherbeautysleep,soshewantstogetbackasquicklyaspossible.FarmerJohn'sfieldhasN(2<=N<=1000)landmarksinit,uniquelynumbered1..N.Landmark1isthebarn;theappletreegroveinwhichBessiestandsalldayislandmarkN.CowstravelinthefieldusingT(1<=T<=2000...
  02014年8月27日3,721dijkstra

• 「BZOJ1324」Exca王者之剑

  

  Description Input第一行给出数字N,M代表行列数.N,M均小于等于100下面N行M列用于描述数字矩阵Output输出最多可以拿到多少块宝石SampleInput221221SampleOutput4题解最小割[crayon-67d074eaad038162604128/]  ...
  02014年8月26日4,924最小割

• 「BZOJ3033」太鼓达人

  

  背景七夕祭上，Vani牵着cl的手，在明亮的灯光和欢乐的气氛中愉快地穿行。这时，在前面忽然出现了一台太鼓达人机台，而在机台前坐着的是刚刚被精英队伍成员XLk、Poet_shy和lydrainbowcat拯救出来的的applepi。看到两人对太鼓达人产生了兴趣，applepi果断闪人，于是cl拿起鼓棒准备挑战。然而即使是在普通难度下，cl的路人本性也充分地暴露了出来。一曲终了，不但没有过关，就连鼓都不灵了。Vani十分过意不去，决定帮助工作人员修...
  02014年8月22日5,299深度搜索,欧拉图

• 「BZOJ2662」[BJ WC2012] 冻结

  

  Description “我要成为魔法少女！”“那么，以灵魂为代价，你希望得到什么？”“我要将有关魔法和奇迹的一切，封印于卡片之中„„”在这个愿望被实现以后的世界里，人们享受着魔法卡片（SpellCard，又名符卡）带来的便捷。现在，不需要立下契约也可以使用魔法了！你还不来试一试？比如，我们在魔法百科全书（Encyclopedia of Spells）里用“freeze”作为关键字来查询，会有很多有趣的结果。例如，我们熟知的Cirno，她的冰...
  02014年8月13日4,861dijkstra

• 「BZOJ3040」最短路(road)

  

  DescriptionN个点，M条边的有向图，求点1到点N的最短路（保证存在）。1<=N<=1000000，1<=M<=10000000Input第一行两个整数N、M，表示点数和边数。第二行六个整数T、rxa、rxc、rya、ryc、rp。前T条边采用如下方式生成：1.初始化x=y=z=0。2.重复以下过程T次：x=(x*rxa+rxc)%rp;y=(y*rya+ryc)%rp;a=min(x%n+1,y%n+1);b=max(y%n+1,y%n+1);则有一条从a到b的，长度为1e8-100*a的有向边。后M-T条边采用读入方式：...
  12014年8月13日8,041dijkstra

• 「BZOJ2594」[Wc2006] 水管局长数据加强版

  

  DescriptionSC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。在...
  52014年8月13日8,122kruskal,离线处理,link cut tree

• NOI2014魔法森林

  

  Description为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护精灵与B型守护精灵。...
  82014年8月12日24,267kruskal,link cut tree

• 「BZOJ2631」tree

  

  Description　一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：+uvc：将u到v的路径上的点的权值都加上自然数c；-u1v1u2v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树；*uvc：将u到v的路径上的点的权值都乘上自然数c；/uv：询问u到v的路径上的点的权值和，求出答案对于51061的余数。Input　　第一行两个整数n，q接下来n-1行每行两个正整数u，v，描述这...
  112014年8月8日8,104link cut tree