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

« 上一页下一页 »Current position : 首页 >> kruskal >> 第2页

• 「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日3,565kruskal

• 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日29,319kruskal,spfa,树上倍增

• 「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,697kruskal

• 「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,293kruskal

• 「CODEVS1403」新三国争霸

  

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

• 「CODEVS1002」搭桥

  

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

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

  

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

• 「JoyOI1307」联络员

  

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

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

  

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

• 「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,816kruskal

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

  

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

• 「vijos1190」繁忙的都市

  

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