网络流 - Page 8

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

网络流费用流总结
1.bzoj狼抓兔子最大流=最小割2.网络流24飞行员配对方案问题二分图最大匹配S向正驾驶员连边，容量1，副驾驶员向T连边，容量1，正驾驶员向可配合的副驾驶员连边，容量1，求最大流3.codevs骑士共存问题最大独立集首先把棋盘黑白染色，使相邻格子颜色不同。把所有可用的黑色格子看做二分图X集合中顶点，可用的白色格子看做Y集合顶点。从S向X集合中每个点连接一条容量为1的有向边，从Y集合中每个点向T连接一条容量为1的有向...
12014年3月26日6,166网络流
「JoyOI1431」分配任务
描述Description随着JoyOI发展越来越大，管理员的任务越来越重，如何合理的分配任务，成为了一个可研究的命题。JoyOI当前一共有M个需要做的任务，和N位管理员。每一个管理员的上线时间并不是固定的，每一个人有d[i]单位的上线时间，每一位管理员一个单位的时间可以完成一个任务，且一个任务只能由一个管理员来完成（如果更多的管理员参与进来，可能会造成混乱）。每一位管理员的能力有所不同，所以能完成的任务集合可能不...
02014年3月26日2,788最大流
「th04」河城荷取
Description在幻想乡，河城荷取是擅长高科技工业的河童。荷取的得意之作除了光学迷彩外，还有震动整个幻想乡的巨型人形『非想天则』。不过由于人形太过巨大，所以为它充能是一件很麻烦的事。人形一共有N个电能池，编号1..N。其中前L个电能池(即编号为1..L的电能池)连接着外部充能接口，而编号为N的电能池连接着动力炉核心。在N个蓄能池之间有M条单向管道，每条管道有一个激活代价cost和电能传输极限limit。当激活度达到某个...
02014年3月23日4,523最大流
「BZOJ3171」[TJOI2013] 循环格
DescriptionInput第一行两个整数R，C。表示行和列，接下来R行，每行C个字符LRUD，表示左右上下。Output一个整数，表示最少需要修改多少个元素使得给定的循环格完美SampleInput34RRRDURLLLRRRSampleOutput2HINT1<=R,L<=15题解可知每个点的出度=入度=1二分图+费用流S向每个点连容量1费用0的边每个点拆出的点向T连容量1，费用0的边每个格子向四周连费用0或1的边[crayon-67405a3a7ade7046022...
02014年3月18日4,642费用流
「BZOJ1934」[SHOI2007] Vote 善意的投票
Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？Input第一行只有两个整数n，m，保证有2...
22014年3月17日4,929最小割
「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,237费用流
「BZOJ1412」[ZJOI2009] 狼和羊的故事
Description“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．”Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。...
02014年3月16日6,683最小割
「BZOJ1221」[HNOI2001] 软件开发
Description某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA,B种消毒方式的费用为每块毛巾fB，而买...
02014年3月16日4,015费用流
「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,115费用流
「网络流24题」负载平衡问题
题目描述 DescriptionG公司有n个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使n个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。«编程任务：对于给定的n个环形排列的仓库的库存量，编程计算使n个仓库的库存数量相同的最少搬运量。输入描述 InputDescription第1行中有1个正整数n（n<=100），表示有n个仓库。第2行中有n个正整数，表示n个仓库的库存量。输出描述 Outpu...
12014年3月11日6,104费用流