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

    「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日38,517线段树,树链剖分,link cut tree
  • 「BZOJ1602」[Usaco2008 Oct] 牧场行走

    「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,307最近公共祖先
  • 「BZOJ1232」[Usaco2008Nov] 安慰奶牛cheer

    「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,440kruskal
  • 「BZOJ1430」小猴打架

    「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,441prufer编码
  • 「fjWC2014」生成树

    「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,046kruskal
  • 「CODEVS1403」新三国争霸

    「CODEVS1403」新三国争霸

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

    02014年2月5日3,427递推与动规,kruskal
  • 「CODEVS1002」搭桥

    「CODEVS1002」搭桥

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

    02014年2月4日4,776kruskal,深度搜索
  • 无聊写的A+B问题。。。

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

    输入A,B输出A+B[crayon-6606a0ec8843f854141538/] 

  • 「JoyOI1307」联络员

    「JoyOI1307」联络员

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

    02014年1月29日3,584kruskal
  • 「BZOJ1821」[JSOI2010] Group 部落划分

    「BZOJ1821」[JSOI2010] Group 部落划分

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

    02014年1月27日5,721kruskal
  • 「BZOJ1601」[Usaco2008 Oct] 灌水

    「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,407kruskal
  • 「CODEVS1001」[BZOJ1050] 舒适的路线

    「CODEVS1001」[BZOJ1050] 舒适的路线

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

    02013年12月21日6,351kruskal,并查集