图论 - Page 30 - hzwer.com

「CODEVS1993」草地排水
题目描述 Description在农夫约翰的农场上，每逢下雨，Bessie最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。农夫约翰知道每一条排水沟每分钟可以流过的水...
32014年1月26日4,874最大流

「CODEVS2822」爱在心中
题目描述 Description“每个人都拥有一个梦，即使彼此不相同，能够与你分享，无论失败成功都会感动。爱因为在心中，平凡而不平庸，世界就像迷宫，却又让我们此刻相逢OurHome。”在爱的国度里有N个人，在他们的心中都有着一个爱的名单，上面记载着他所爱的人（不会出现自爱的情况）。爱是具有传递性的，即如果A爱B，B爱C，则A也爱C。如果有这样一部分人，他们彼此都相爱，则他们就超越了一切的限制，用集体的爱化身成为一...
02014年1月26日3,870图的连通
NOI2006最大获利
题目描述 Description新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后，公司得到了一共N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一...
42014年1月18日7,012最小割
「CODEVS1021」玛丽卡
题目描述 Description麦克找了个新女朋友，玛丽卡对他非常恼火并伺机报复。因为她和他们不住在同一个城市，因此她开始准备她的长途旅行。在这个国家中每两个城市之间最多只有一条路相通，并且我们知道从一个城市到另一个城市路上所需花费的时间。麦克在车中无意中听到有一条路正在维修，并且那儿正堵车，但没听清楚到底是哪一条路。无论哪一条路正在维修，从玛丽卡所在的城市都能到达麦克所在的城市。玛丽卡将只从不堵车的路上通...
42014年1月16日4,452spfa
「BZOJ1295」[SCOI2009] 最长距离
Descriptionwindy有一块矩形土地，被分为N*M块1*1的小格子。有的格子含有障碍物。如果从格子A可以走到格子B，那么两个格子的距离就为两个格子中心的欧几里德距离。如果从格子A不可以走到格子B，就没有距离。如果格子X和格子Y有公共边，并且X和Y均不含有障碍物，就可以从X走到Y。如果windy可以移走T块障碍物，求所有格子间的最大距离。保证移走T块障碍物以后，至少有一个格子不含有障碍物。Input输入文件maxlength....
22014年1月16日4,393spfa
「BZOJ1491」[NOI2007] 社交网络
DescriptionInputOutput输出文件包括n行，每行一个实数，精确到小数点后3位。第i行的实数表示结点i在社交网络中的重要程度。SampleInput44121231341411SampleOutput1.0001.0001.0001.000HINT为1代码[crayon-67481c7871391678305953/] ...
02014年1月15日5,098floyd
「网络流24题」搭配飞行员(飞行员配对方案问题)
「问题描述」飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员,需一个正驾驶员和一个副驾驶员。由于种种原因，例如相互配合的问题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多。如图，假设有10个驾驶员，如图中的V1，V2，…，V10就代表达10个驾驶员,其中V1，V2，V3，V4，V5是正驾驶员,V6，V7，V8，V9，V10是副驾驶员。如果一个正驾驶员和...
22014年1月10日7,142最小割
「BZOJ1001」[BJ2006] 狼抓兔子
Description现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路1:(x,y)<==>(x+1,y)2:(x,y)<==>(x,y+1)3:(x,y)<==>(x+1,y+1)道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的.左上角和右下角为...
32014年1月9日26,850最小割,spfa
「BZOJ1051」[HAOI2006] 受欢迎的牛
Description每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。Input第一行两个数N,M。接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A,B）Output一个数，即有多少头牛被...
42014年1月8日10,300图的连通
「BZOJ1202」[HNOI2005] 狡猾的商人
Description刁姹接到一个任务，为税务部门调查一位商人的账本，看看账本是不是伪造的。账本上记录了n个月以来的收入情况，其中第i个月的收入额为Ai(i=1,2,3...n-1,n)，。当Ai大于0时表示这个月盈利Ai元，当Ai小于0时表示这个月亏损Ai元。所谓一段时间内的总收入，就是这段时间内每个月的收入额的总和。刁姹的任务是秘密进行的，为了调查商人的账本，她只好跑到商人那里打工。她趁商人不在时去偷看账本，可是她无法将账本偷出...
02014年1月7日6,936并查集
「BZOJ1059」[ZJOI2007] 矩阵游戏
Description小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）列交换操作：选择矩阵的任意行列，交换这两列（即交换对应格子的颜色）游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的...
02014年1月7日6,346二分图匹配
并查集学习总结
在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受，只能采用一种全新的抽象的特殊数据结构——并查集来描述。初始化把每个点所在集合初始化为其自身。father[i]=i;通常来说，这个步骤在每次使用该数据结...
02014年1月7日5,324并查集