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

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

• 「JoyOI1863」[Poetize I] 黑魔法师之门

  

  背景Background经过了16个工作日的紧张忙碌，未来的人类终于收集到了足够的能源。然而在与Violet星球的战争中，由于Z副官的愚蠢，地球的领袖applepi被邪恶的黑魔法师Vani囚禁在了Violet星球。为了重启Nescafé这一宏伟的科技工程，人类派出了一支由XLk、Poet_shy和lydrainbowcat三人组成的精英队伍，穿越时空隧道，去往Violet星球拯救领袖applepi。描述Descriptionapplepi被囚禁的地点只有一扇门，当地人称它为“黑魔法...
  52014年5月23日4,238并查集

• 「BZOJ1626」[Usaco2007 Dec] Building Roads 修建道路

  

  DescriptionFarmerJohn最近得到了一些新的农场，他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达（也就是说，从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场）。有些农场之间原本就有道路相连。所有N(1<=N<=1,000)个农场（用1..N顺次编号）在地图上都表示为坐标为(X_i,Y_i)的点(0<=X_i<=1,000,000；0<=Y_i<=1,000,000)，两个农场间道路的长度自然就是代表它们的点之间...
  02014年5月23日4,122kruskal

• 「1612」[Usaco2008 Jan] Cow Contest奶牛的比赛

  

  DescriptionFJ的N(1<=N<=100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1<=A<=N;1<=B<=N;A!=B)，那么她们的对决中，编号为A的奶牛总是能胜出。F...
  02014年5月22日5,577floyd

• 「BZOJ1711」[Usaco2007 Open] Dingin吃饭

  

  Description农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食.每一头牛只喜欢吃一些食品和饮料而别的一概不吃.虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料.农夫JOHN做了F(1<=F<=100)种食品并准备了D(1<=D<=100)种饮料.他的N(1<=N<=100)头牛都以决定了是否愿意吃某种食物和喝某种饮料.农夫JOHN想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物...
  02014年5月20日4,175最大流

• 「BZOJ1690」[Usaco2007 Dec] 奶牛的旅行

  

  Description作为对奶牛们辛勤工作的回报，FarmerJohn决定带她们去附近的大城市玩一天。旅行的前夜，奶牛们在兴奋地讨论如何最好地享受这难得的闲暇。很幸运地，奶牛们找到了一张详细的城市地图，上面标注了城市中所有L(2<=L<=1000)座标志性建筑物（建筑物按1..L顺次编号），以及连接这些建筑物的P(2<=P<=5000)条道路。按照计划，那天早上FarmerJohn会开车将奶牛们送到某个她们指定的建筑物旁边，等奶牛们完成...
  32014年5月19日5,210spfa

• 「BZOJ2429」[HAOI2006] 聪明的猴子

  

  Description在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地表还是被大水淹没着，部分植物的树冠露在水面上。猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面的不同树冠上来回穿梭，以找到喜欢吃的果实。现在，在这个地区露出水面的有N棵树，假设每棵树本身的直径都很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示...
  02014年5月18日5,216kruskal

• 「BZOJ1529」[POI2005] ska Piggy banks

  

  DescriptionByteazar有N个小猪存钱罐.每个存钱罐只能用钥匙打开或者砸开.Byteazar已经把每个存钱罐的钥匙放到了某些存钱罐里.Byteazar现在想买一台汽车于是要把所有的钱都取出来.他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.Input第一行一个整数N(1<=N<=1.000.000)–表示存钱罐的总数.接下来每行一个整数,第i+1行的整数代表第i个存钱罐的钥匙放置的存钱罐编号.Output一个整数表示最少打破多少个存...
  02014年5月17日5,081并查集,图的连通

• 「BZOJ2208」[JSOI2010] 连通数

  

  DescriptionInput输入数据第一行是图顶点的数量，一个正整数N。接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。Output输出一行一个整数，表示该图的连通数。SampleInput3010001100SampleOutput9HINT对于100%的数据，N不超过2000。题解据说此题暴力是可过的，复杂度O（nm）正解似乎是先缩点完然后递推[crayon-6743b99908f2a660404285/] ...
  42014年5月15日6,126图的连通

• 「BZOJ1116」[POI2008] CLO

  

  DescriptionByteotia城市有n个townsm条双向roads.每条road连接两个不同的towns,没有重复的road.你要把其中一些road变成单向边使得：每个town都有且只有一个入度Input第一行输入nm.1<=n<=100000,1<=m<=200000下面M行用于描述M条边.OutputTAK或者NIE常做POI的同学,应该知道这两个单词的了...SampleInput451223133414SampleOutputTAK上图给出了一种连接方式.题解这题令我突然想到了scoi游戏首先我们...
  02014年5月13日5,134并查集

• 「BZOJ1016」[JSOI2008] 最小生成树计数

  

  Description现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。Input第一行包含两个数，n和m，其中1<=n<=100;1<=m<=1000;表示该无向图的节点数和边数。每个节点用1~n的整数编号。接下来的m行，每...
  52014年5月13日19,726kruskal,深度搜索

• 「NOIP模拟赛」虫洞

  

  「题目描述」N个虫洞，M条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和1单位时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为delta。从白洞跃迁到黑洞，消耗的燃料值减少delta，若该条路径消耗的燃料值变为负数的话，取为0。从黑洞跃迁到白洞，消耗的燃料值增加delta。路径两端均为黑洞或白洞，消耗的燃料值不变化。作为压轴题，自然不会是如此简单的最短路问题，所以每过1单位时间黑洞...
  02014年5月10日5,226spfa

• 「BZOJ1458」士兵占领

  

  Description有一个M*N的棋盘，有的格子是障碍。现在你要选择一些格子来放置一些士兵，一个格子里最多可以放置一个士兵，障碍格里不能放置士兵。我们称这些士兵占领了整个棋盘当满足第i行至少放置了Li个士兵,第j列至少放置了Cj个士兵。现在你的任务是要求使用最少个数的士兵来占领整个棋盘。Input第一行两个数M,N,K分别表示棋盘的行数，列数以及士兵的个数。第二行有M个数表示Li。第三行有N个数表示Ci。接下来有K行，...
  02014年5月10日4,446最大流