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

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

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

• 「BZOJ1624」[Usaco2008 Open] Clear And Present Danger 寻宝之路

  

  Description    农夫约翰正驾驶一条小艇在牛勒比海上航行．    海上有N(1≤N≤100)个岛屿，用1到N编号．约翰从1号小岛出发，最后到达N号小岛．一张藏宝图上说，如果他的路程上经过的小岛依次出现了Ai，A2，…，AM(2≤M≤10000)这样的序列（不一定相邻），那他最终就能找到古老的宝藏．  但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗出没的概率，他用一个危险指数Dij(0≤Dij≤100000...
  02014年4月4日3,571floyd

• 「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,464prufer编码

• 「网络流24题」航空计划

  

  «问题描述：给定一张航空图，图中顶点代表城市，边代表2城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。(1)从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点(可途经若干城市)。(2)除起点城市外，任何城市只能访问1次。«编程任务：对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。«数据输入：由文件airl.in提供输入数据。文件第1行...
  12014年4月3日3,308费用流

• 「BZOJ2127」happiness

  

  Description高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。Input第一行两个正整数n，m。接下来是六个矩阵第一个矩阵为n行m列此矩阵的第i行第j列的数字...
  22014年3月31日7,692最小割

• 「BZOJ2132」圈地计划

  

  Description最近房地产商GDOI(GroupofDumbbellsOrIdiots)从NOI(NutsOldIdiots)手中得到了一块开发土地。据了解，这块土地是一块矩形的区域，可以纵横划分为N×M块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境，每块小区域建造商业区和工业区能取得不同的经济价值。更具体点，对于第i行第j列的区域，建造商业区将得到Aij收益，建造工业区将得到Bij收益。另外不同的区域连在一起...
  02014年3月31日6,384最小割

• 「BZOJ1433」[ZJOI2009] 假期的宿舍

  

  DescriptionInputOutputSampleInput13110010011100100SampleOutputˆˆHINT对于30%的数据满足1≤n≤12。对于100%的数据满足1≤n≤50,1≤T≤20。题解源点向所有有床位的连边需要床位的向汇点连边如果i可以睡j的床i向j‘连边[crayon-664aba1d9067e318214119/] ...
  02014年3月27日4,592最大流

• 网络流费用流总结

  

  1.bzoj狼抓兔子最大流=最小割2.网络流24飞行员配对方案问题 二分图最大匹配S向正驾驶员连边，容量1，副驾驶员向T连边，容量1，正驾驶员向可配合的副驾驶员连边，容量1，求最大流3.codevs骑士共存问题 最大独立集首先把棋盘黑白染色，使相邻格子颜色不同。把所有可用的黑色格子看做二分图X集合中顶点，可用的白色格子看做Y集合顶点。从S向X集合中每个点连接一条容量为1的有向边，从Y集合中每个点向T连接一条容量为1的有向...
  12014年3月26日5,992网络流

• 「JoyOI1431」分配任务

  

  描述Description随着JoyOI发展越来越大，管理员的任务越来越重，如何合理的分配任务，成为了一个可研究的命题。JoyOI当前一共有M个需要做的任务，和N位管理员。每一个管理员的上线时间并不是固定的，每一个人有d[i]单位的上线时间，每一位管理员一个单位的时间可以完成一个任务，且一个任务只能由一个管理员来完成（如果更多的管理员参与进来，可能会造成混乱）。每一位管理员的能力有所不同，所以能完成的任务集合可能不...
  02014年3月26日2,647最大流

• 「BZOJ2763」[JLOI2011] 飞行路线

  

  DescriptionAlice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？Input数据的第一行有三个整...
  02014年3月25日5,230spfa

• 「th04」河城荷取

  

  Description在幻想乡，河城荷取是擅长高科技工业的河童。荷取的得意之作除了光学迷彩外，还有震动整个幻想乡的巨型人形『非想天则』。不过由于人形太过巨大，所以为它充能是一件很麻烦的事。人形一共有N个电能池，编号1..N。其中前L个电能池(即编号为1..L的电能池)连接着外部充能接口，而编号为N的电能池连接着动力炉核心。在N个蓄能池之间有M条单向管道，每条管道有一个激活代价cost和电能传输极限limit。当激活度达到某个...
  02014年3月23日4,314最大流

• 「JoyOI1460」旅行

  

  描述DescriptionA国有n座城市，每座城市都十分美，这使得A国的民众们非常喜欢旅行。然而，A国的交通十分落后，这里只有m条双向的道路，并且这些道路都十分崎岖，有的甚至还是山路，只能靠步行。通过每条道路的长度、泥泞程度等因素，我们给每条道路评估一个“崎岖度”，表示通过这条道路的不舒适程度。从X城市经过若干条道路到达Y城市，我们称这次旅行的“代价”为所经过道路“崎岖度”的最大值。当然，如果从X城市到Y城市...
  112014年3月20日4,630二分法,并查集