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

« 上一页下一页 »Current position : 首页 >> 树 >> 第8页

• 「BZOJ1036」[ZJOI2008] 树的统计Count

  

  Description一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作：I.CHANGEut:把结点u的权值改为tII.QMAXuv:询问从点u到点v的路径上的节点的最大权值III.QSUMuv:询问从点u到点v的路径上的节点的权值和注意：从点u到点v的路径上的节点包括u和v本身Input输入的第一行为一个整数n，表示节点的个数。接下来n–1行，每行2个整数a和b，表示节点a和节点b之...
  272014年4月6日39,520线段树,树链剖分,link cut tree

• 「BZOJ1602」[Usaco2008 Oct] 牧场行走

  

  DescriptionN头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。这n块土地被n-1条边连接。奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的...
  02014年4月6日4,578最近公共祖先

• 「BZOJ1232」[Usaco2008Nov] 安慰奶牛cheer

  

  DescriptionFarmerJohn变得非常懒,他不想再继续维护供奶牛之间供通行的道路.道路被用来连接N(5<=N<=10,000)个牧场,牧场被连续地编号为1..N.每一个牧场都是一个奶牛的家.FJ计划除去P(N-1<=P<=100,000)条道路中尽可能多的道路,但是还要保持牧场之间的连通性.你首先要决定那些道路是需要保留的N-1条道路.第j条双向道路连接了牧场S_j和E_j(1<=S_j<=N;1<=E_j<=N;S_j!=E_j),而且走完它需要L...
  02014年4月5日5,727kruskal

• 「BZOJ1430」小猴打架

  

  Description一开始森林里面有N只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过N-1次打架之后，整个森林的小猴都会成为好朋友。现在的问题是，总共有多少种不同的打架过程。比如当N=3时，就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的打架过程。Input一个整数N。Output一行，方案数mod9999991。Sample...
  02014年4月3日3,584prufer编码

• 「fjWC2014」生成树

  

  Description给定一个无向图，要求图中一个生成树，这个生成树中的最大边和最小边相差最小，输出这个差值 Input每组测试数据一组样例每组样例首先输入两个整数n,m (3≤ n ≤ 300,0< m ≤ n*(n-1)/2)，表示该组样例中点和边的个数，之后每行三个整数x,y,s (0≤ x ≤ n-1,0≤ y ≤ n-1,1≤ s ≤ 10000)，表示编号为x和编号为y的点之间有一条长度为s的边相连，保证给定的图联通，任意两点之间只有一条边相连...
  02014年2月16日14,330kruskal

• 「CODEVS1403」新三国争霸

  

  题目描述 DescriptionPP特别喜欢玩即时战略类游戏，但他觉得那些游戏都有美中不足的地方。灾害总不降临道路，而只降临城市，而且道路不能被占领，没有保护粮草的真实性。于是他就研发了《新三国争霸》。在这款游戏中，加入灾害对道路的影响（也就是一旦道路W[i，j]受到了灾害的影响，那么在一定时间内，这条路将不能通过）和道路的占领权（对于一条道路W[i，j]，至少需要K[i，j]个士兵才能守住）。PP可真是高手，不一会，...
  02014年2月5日3,744递推与动规,kruskal

• 「CODEVS1002」搭桥

  

  题目描述 Description有一矩形区域的城市中建筑了若干建筑物，如果某两个单元格有一个点相联系，则它们属于同一座建筑物。现在想在这些建筑物之间搭建一些桥梁，其中桥梁只能沿着矩形的方格的边沿搭建，如下图城市1有5栋建筑物，可以搭建4座桥将建筑物联系起来。城市2有两座建筑物，但不能搭建桥梁将它们连接。城市3只有一座建筑物，城市4有3座建筑物，可以搭建一座桥梁联系两栋建筑物，但不能与第三座建筑物联系在一起。输入描述...
  02014年2月4日5,238kruskal,深度搜索

• 无聊写的A+B问题。。。

  

  输入A,B输出A+B[crayon-6768b84f2128f213942692/] 
  42014年2月3日9,070spfa,最小割,kruskal,背包动规,线段树,floyd,树状数组

• 「JoyOI1307」联络员

  

  [crayon-6768b84f21aaf701423201/] 描述DescriptionJoyOI已经一岁了，网站也由最初的几个用户增加到了上万个用户，随着JoyOI网站的逐步壮大，管理员的数目也越来越多，现在你身为JoyOI管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。JoyOI是一个公益性的网站，没有过多的利润，所以你要尽可能的使费用少才可以。  目前你已经知道，JoyOI的通信渠道分为两大类...
  02014年1月29日3,881kruskal

• 「BZOJ1821」[JSOI2010] Group 部落划分

  

  Description聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了N个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，...
  02014年1月27日6,022kruskal

• 「BZOJ1601」[Usaco2008 Oct] 灌水

  

  DescriptionFarmerJohn已经决定把水灌到他的n(1<=n<=300)块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0).计算FarmerJohn所需的最少代价。Input*第一行：一个数n*第二行到第n+1行：第i+1行含有一个数wi*第n+2行到第2n+1行：第n+1+i行有n个被空格分开的...
  32014年1月5日5,857kruskal

• 「CODEVS1001」[BZOJ1050] 舒适的路线

  

  题目描述DescriptionZ小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。Z小镇附近共有N(1<N≤500)个景点（编号为1,2,3,…,N），这些景点被M（0<M≤5000）条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。也许是为了保护该地的旅游资源，Z小镇有个奇怪的规定，就是对于一条给定的公路Ri，任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服，因此大家从一个景...
  02013年12月21日6,807kruskal,并查集