• 「BZOJ3390」[Usaco2004 Dec] Bad Cowtractors牛的报复

    「BZOJ3390」[Usaco2004 Dec] Bad Cowtractors牛的报复

    Description    奶牛贝茜被雇去建设N(2≤N≤1000)个牛棚间的互联网.她已经勘探出M(1≤M≤20000)条可建的线路,每条线路连接两个牛棚,而且会苞费C(1≤C≤100000).农夫约翰吝啬得很,他希望建设费用最少甚至他都不想给贝茜工钱. 贝茜得知工钱要告吹,决定报复.她打算选择建一些线路,把所有牛棚连接在一起,让约翰花费最大.但是她不能造出环来,这样约翰就会发现.Input  第1行:N,M.  第2到M+1行:三个整...

    02014年4月15日1,952kruskal
  • NOIP2013货车运输

    NOIP2013货车运输

    题目描述DescriptionA国有n座城市,编号从1到n,城市之间有m条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有q辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。输入描述InputDescription第一行有两个用一个空格隔开的整数n,m,表示A国有n座城市和m条道路。接下来m行每行3个整数x、y、z,每两个整数之间用一个空格隔开,表示从x号城市到y号城市有一条限重为z的道路。注意:x...

    142014年4月9日11,810kruskal,spfa,树上倍增
  • 「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日3,780kruskal
  • 「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日1,988kruskal
  • 「CODEVS1403」新三国争霸

    「CODEVS1403」新三国争霸

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

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

    「CODEVS1002」搭桥

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

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

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

    输入A,B输出A+B[crayon-5ba4fd0446844720848680/] 

  • 「JoyOI1307」联络员

    「JoyOI1307」联络员

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

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

    「BZOJ1821」[JSOI2010] Group 部落划分

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

    02014年1月27日3,584kruskal
  • 「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个被空格分开的...

    42014年1月5日3,341kruskal
  • 「CODEVS1001」[BZOJ1050] 舒适的路线

    「CODEVS1001」[BZOJ1050] 舒适的路线

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

    02013年12月21日4,568kruskal,并查集
  • 「vijos1190」繁忙的都市

    「vijos1190」繁忙的都市

    描述城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的...

    02013年12月20日2,240kruskal