图论 - Page 26 - hzwer.com

「POJ2588」Snakes
DescriptionBuffaloBillwishestocrossa1000x1000squarefield.Anumberofsnakesareonthefieldatvariouspositions,andeachsnakecanstrikeaparticulardistanceinanydirection.CanBillmakethetripwithoutbeingbitten?InputAssumethatthesouthwestcornerofthefieldisat(0,0)andthenorthwestcornerat(0,1000).Theinputconsistsofalinecontainingn<=1000,thenumberofsnakes.Alinefollowsforeachsnake,containingthreerealnumb...
02014年3月19日3,213并查集

「BZOJ3171」[TJOI2013] 循环格
DescriptionInput第一行两个整数R，C。表示行和列，接下来R行，每行C个字符LRUD，表示左右上下。Output一个整数，表示最少需要修改多少个元素使得给定的循环格完美SampleInput34RRRDURLLLRRRSampleOutput2HINT1<=R,L<=15题解可知每个点的出度=入度=1二分图+费用流S向每个点连容量1费用0的边每个点拆出的点向T连容量1，费用0的边每个格子向四周连费用0或1的边[crayon-6743852658f5b858196...
02014年3月18日4,643费用流
「BZOJ1934」[SHOI2007] Vote 善意的投票
Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？Input第一行只有两个整数n，m，保证有2...
22014年3月17日4,931最小割
「BZOJ2424」[HAOI2010] 订货
Description某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S。 Input第1行：n,m,S(0<=n<=50,0<=m<=10,0<=S<=100...
02014年3月17日4,240费用流
「BZOJ1412」[ZJOI2009] 狼和羊的故事
Description“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．”Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。...
02014年3月16日6,685最小割
「BZOJ1221」[HNOI2001] 软件开发
Description某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA,B种消毒方式的费用为每块毛巾fB，而买...
02014年3月16日4,017费用流
「BZOJ1305」[CQOI2009] dance跳舞
Description一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？Input第一行包含两个整数n和k。以下n行每行包含n个字符，其...
02014年3月13日7,315二分法,最大流
「网络流24题」分配问题
题目描述 Description有n件工作要分配给n个人做。第i个人做第j件工作产生的效益为ijc。试设计一个将n件工作分配给n个人做的分配方案，使产生的总效益最大。«编程任务：对于给定的n件工作和n个人，计算最优分配方案和最差分配方案。输入描述 InputDescription第1行有1个正整数n，表示有n件工作要分配给n个人做。接下来的n行中，每行有n个整数cij，1≤i≤n，1≤j≤n，表示第i个人做第j件工作产生的效益为cij输出描述 OutputD...
02014年3月11日5,119费用流
「网络流24题」负载平衡问题
题目描述 DescriptionG公司有n个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使n个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。«编程任务：对于给定的n个环形排列的仓库的库存量，编程计算使n个仓库的库存数量相同的最少搬运量。输入描述 InputDescription第1行中有1个正整数n（n<=100），表示有n个仓库。第2行中有n个正整数，表示n个仓库的库存量。输出描述 Outpu...
12014年3月11日6,106费用流
「BZOJ3245」最快路线
Description精明的小R每每开车出行总是喜欢走最快路线,而不是最短路线.很明显,每条道路的限速是小R需要考虑的关键问题.不过有一些限速标志丢失了,于是小R将不知道能开多快.不过有一个合理的方法是进入这段道路时不改变速度行驶.你的任务就是计算从小R家(0号路口)到D号路口的最快路线.现在你得到了这个城市的地图,这个地图上的路都是单向的,而且对于两个路口A和B,最多只有一条道路从A到B.并且假设可以瞬间完成路口的转弯和...
02014年3月10日4,642spfa
「网络流24题」汽车加油行驶问题
题目描述 Description给定一个N*N的方形网格，设其左上角为起点◎，坐标为（1，1），X轴向右为正，Y轴向下为正，每个方格边长为1，如图所示。一辆汽车从起点◎出发驶向右下角终点▲，其坐标为（N，N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则：(1)汽车只能沿网格边行驶，装满油后能行驶K条网格边。出发时汽车已装满油，在起点与终点处不设油库。(2)汽车经过一条网格...
02014年3月8日4,890spfa
「网络流24题」餐巾计划问题
题目描述 Description一个餐厅在相继的N天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f分；或者送到慢洗部，洗一块需n天(n>m)，其费用为s<f分。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，...
02014年3月8日7,290费用流